#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define dbg(x) cerr << #x << " is " << x << "\n";
using ll = long long;
using ii = pair<ll,ll>;
const int N = 101;
const int L = 1010;
const int MOD = 1e9+7;
int n, lim, a[N];
ll dp[3][N][N][L];
ll DP(int lr, int i, int comp, int curans) {
if(curans > lim) return 0;
if(i > n) return lr == 2 && comp == 1;
ll &ret = dp[lr][i][comp][curans];
if(ret != -1) return ret;
ret = 0;
if(lr < 2) { // put a[i] at one of the free endpoints
if(i == n) { // special situation where we have to merge with the other end
ret += DP(lr + 1, i + 1, comp, curans + (2 * comp - lr - 1) * (a[i + 1] - a[i]));
ret %= MOD;
}
// we can choose to merge it too (there has to be another endpoint free component for that)
else if(comp - lr > 0) {
ret += (2 - lr) * (comp - lr) * DP(lr + 1, i + 1, comp, curans + (2 * comp - lr - 1) * (a[i + 1] - a[i]));
ret %= MOD;
}
// it can be a new component
ret += (2 - lr) * DP(lr + 1, i + 1, comp + 1, curans + (2 * comp - lr + 1) * (a[i + 1] - a[i]));
ret %= MOD;
}
if(i <= n - 2) { // this number can create a new cc in middle
ret += DP(lr, i + 1, comp + 1, curans + (2 * comp - lr + 2) * (a[i + 1] - a[i]));
ret %= MOD;
}
if(i <= n - 1 && comp > 0) { // this number can merge with one component
ret += (2 * comp - lr) * DP(lr, i + 1, comp, curans + (2 * comp - lr) * (a[i + 1] - a[i]));
ret %= MOD;
}
if(comp >= 2) { // this number can merge two components together
// but there are some caseworks with lr
if(lr == 0) {
// P(comp, 2) ways
ret += (1LL * comp * (comp - 1)) * DP(lr, i + 1, comp - 1, curans + (2 * comp - lr - 2) * (a[i + 1] - a[i]));
ret %= MOD;
}
else if(lr == 1) {
// P(comp - 1, 2) + comp - 1 = (comp - 1)^2
ret += (1LL * (comp - 1) * (comp - 1)) * DP(lr, i + 1, comp - 1, curans + (2 * comp - lr - 2) * (a[i + 1] - a[i]));
ret %= MOD;
}
else {
// you cant add the leftmost and rightmost endpoints before everything in the middle is merged
if(i == n) { // only time you can merge left-end with right-end
ret += DP(lr, i + 1, comp - 1, curans + (2 * comp - lr - 2) * (a[i + 1] - a[i]));
ret %= MOD;
}
else { // P(comp - 2, 2) + 2 * (comp - 2) = (comp - 1) * (comp - 2)
ret += (1LL * (comp - 1) * (comp - 2)) * DP(lr, i + 1, comp - 1, curans + (2 * comp - lr - 2) * (a[i + 1] - a[i]));
ret %= MOD;
}
}
}
return ret;
}
int main() {
scanf("%d %d", &n, &lim);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
sort(a + 1, a + n + 1);
a[n + 1] = a[n];
memset(dp, -1, sizeof dp);
printf("%lld\n", DP(0, 1, 0, 0));
return 0;
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
81 | scanf("%d %d", &n, &lim);
| ~~~~~^~~~~~~~~~~~~~~~~~~
skyscraper.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
83 | scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
135 ms |
242296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
135 ms |
242296 KB |
Output is correct |
| 2 |
Correct |
136 ms |
242296 KB |
Output is correct |
| 3 |
Correct |
137 ms |
242296 KB |
Output is correct |
| 4 |
Correct |
145 ms |
242296 KB |
Output is correct |
| 5 |
Correct |
139 ms |
242296 KB |
Output is correct |
| 6 |
Correct |
135 ms |
242296 KB |
Output is correct |
| 7 |
Correct |
133 ms |
242296 KB |
Output is correct |
| 8 |
Correct |
148 ms |
242424 KB |
Output is correct |
| 9 |
Correct |
133 ms |
242296 KB |
Output is correct |
| 10 |
Correct |
134 ms |
242296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
135 ms |
242296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
