Kevin_Zhang

Untitled

Dec 17th, 2020
984
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.98 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define pb emplace_back
  3. #define AI(i) begin(i), end(i)
  4. template<class T>
  5. bool chmax(T &val, T nv) {
  6.     return val < nv ? (val = nv, true) : false;
  7. }
  8. template<class T>
  9. bool chmin(T &val, T nv) {
  10.     return nv < val ? (val = nv, true) : false;
  11. }
  12. using namespace std;
  13. using ll = long long;
  14. #ifdef KEV
  15. #define DE(args...) kout("[ " + string(#args) + " ] = ", args)
  16. void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
  17. void kout(){ cerr << endl; }
  18. template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
  19. #else
  20. #define DE(...) 0
  21. #define debug(...) 0
  22. #endif
  23. // What I should check
  24. // 1. overflow
  25. // 2. corner cases
  26. // Enjoy the problem instead of hurrying to AC
  27. // Good luck !
  28. const int MAX_N = 210, MAX_K = 1010, p = 1e9 + 7;
  29.  
  30. ll dp[MAX_N][MAX_K], tmp[MAX_N][MAX_K];
  31. int n, k, a[MAX_N];
  32. void add(ll &v, ll a) { v += a - p; if (v < 0) v += p; }
  33. int32_t main() {
  34.     ios_base::sync_with_stdio(0), cin.tie(0);
  35.     cin >> n >> k;
  36.     for (int i = 1;i <= n;++i)
  37.         cin >> a[i];
  38.  
  39.     sort(a+1, a+1+n);
  40.  
  41.     auto dp = ::dp, tmp = ::tmp;
  42.  
  43.     dp[0][0] = 1;
  44.  
  45.     for (int i = 0;i < n;++i) {
  46.         int dis = a[i+1] - a[i];
  47.         memset(tmp, 0, sizeof(tmp));
  48.  
  49.         //DE(i, a[i+1]);
  50.  
  51.         for (int j = 0;j <= n;++j)
  52.             for (int l = 0;l <= k;++l) if (dp[j][l]) {
  53.                 int ncost = l + j * dis;
  54.                 if (ncost > k) break;
  55.                 // if the number of the groups doesn't change
  56.                 // I can join one of the groups
  57.                 add(tmp[j][ ncost ], dp[j][l] * j % p);
  58.  
  59.                 // or I can make a group with me only
  60.                 add(tmp[j][ ncost ], dp[j][l]);
  61.  
  62.  
  63.                 // if the number of the groups add by one
  64.                 // I must be creating a new group
  65.                 add(tmp[j + 1][ ncost ], dp[j][l]);
  66.  
  67.                 // if the number of the groups decrease by one
  68.                 // I must end one of the groups
  69.                 if (j) {
  70.                     add(tmp[j - 1][ ncost ], dp[j][l] * j % p);
  71.                 }
  72.             }
  73.         swap(tmp, dp);
  74.     }
  75.  
  76.     ll sum = 0;
  77.  
  78.     for (int i = 0;i <= k;++i) add(sum, dp[0][i]);
  79.  
  80.     cout << sum << '\n';
  81.  
  82. }
  83.  
Advertisement
Add Comment
Please, Sign In to add comment