Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define pb emplace_back
- #define AI(i) begin(i), end(i)
- template<class T>
- bool chmax(T &val, T nv) {
- return val < nv ? (val = nv, true) : false;
- }
- template<class T>
- bool chmin(T &val, T nv) {
- return nv < val ? (val = nv, true) : false;
- }
- using namespace std;
- using ll = long long;
- #ifdef KEV
- #define DE(args...) kout("[ " + string(#args) + " ] = ", args)
- void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
- void kout(){ cerr << endl; }
- template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
- #else
- #define DE(...) 0
- #define debug(...) 0
- #endif
- // What I should check
- // 1. overflow
- // 2. corner cases
- // Enjoy the problem instead of hurrying to AC
- // Good luck !
- const int MAX_N = 210, MAX_K = 1010, p = 1e9 + 7;
- ll dp[MAX_N][MAX_K], tmp[MAX_N][MAX_K];
- int n, k, a[MAX_N];
- void add(ll &v, ll a) { v += a - p; if (v < 0) v += p; }
- int32_t main() {
- ios_base::sync_with_stdio(0), cin.tie(0);
- cin >> n >> k;
- for (int i = 1;i <= n;++i)
- cin >> a[i];
- sort(a+1, a+1+n);
- auto dp = ::dp, tmp = ::tmp;
- dp[0][0] = 1;
- for (int i = 0;i < n;++i) {
- int dis = a[i+1] - a[i];
- memset(tmp, 0, sizeof(tmp));
- //DE(i, a[i+1]);
- for (int j = 0;j <= n;++j)
- for (int l = 0;l <= k;++l) if (dp[j][l]) {
- int ncost = l + j * dis;
- if (ncost > k) break;
- // if the number of the groups doesn't change
- // I can join one of the groups
- add(tmp[j][ ncost ], dp[j][l] * j % p);
- // or I can make a group with me only
- add(tmp[j][ ncost ], dp[j][l]);
- // if the number of the groups add by one
- // I must be creating a new group
- add(tmp[j + 1][ ncost ], dp[j][l]);
- // if the number of the groups decrease by one
- // I must end one of the groups
- if (j) {
- add(tmp[j - 1][ ncost ], dp[j][l] * j % p);
- }
- }
- swap(tmp, dp);
- }
- ll sum = 0;
- for (int i = 0;i <= k;++i) add(sum, dp[0][i]);
- cout << sum << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment