#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int L = 1005;
const int MOD = 1000000007;
int dp[N][L][N][2][2], a[N], n, lim;
int add(int x, int y) {
if ((x += y) >= MOD) x -= MOD;
return x;
}
int mul(int x, int y) {
return (long long)x * y % MOD;
}
int calc(int i, int cSum, int cMid, int cLef, int cRig) {
int &res = dp[i][cSum][cMid][cLef][cRig];
if (res >= 0) return res; res = 0;
/// assume missing position is filled with a[i + 1]
int nSum = cSum + (cMid * 2 + cLef + cRig) * (a[i + 1] - a[i]);
if (nSum > lim || cMid < 0) return res = 0;
/// concate left segment and right segment
if (i == n - 1) return res = cMid == 0;
/// append to left segment
res = add(res, calc(i + 1, nSum, cMid, 1, cRig));
/// append to right segment
res = add(res, calc(i + 1, nSum, cMid, cLef, 1));
/// create new mid segment
res = add(res, mul(calc(i + 1, nSum, cMid + 1, cLef, cRig), cMid + 1));
/// append to mid segment
res = add(res, mul(calc(i + 1, nSum, cMid, cLef, cRig), cMid * 2));
/// concate two adjacent mid segments
res = add(res, mul(calc(i + 1, nSum, cMid - 1, cLef, cRig), cMid - 1));
/// concate left segment and leftest mid segment
res = add(res, calc(i + 1, nSum, cMid - 1, 1, cRig));
/// concate right segment and rightest mid segment
res = add(res, calc(i + 1, nSum, cMid - 1, cLef, 1));
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> lim;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
memset(dp, -1, sizeof dp);
cout << calc(0, 0, 0, 0, 0) << '\n';
}
Compilation message
skyscraper.cpp: In function 'int calc(int, int, int, int, int)':
skyscraper.cpp:22:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
22 | if (res >= 0) return res; res = 0;
| ^~
skyscraper.cpp:22:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
22 | if (res >= 0) return res; res = 0;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
95 ms |
173964 KB |
Output is correct |
| 2 |
Correct |
95 ms |
173952 KB |
Output is correct |
| 3 |
Correct |
92 ms |
173804 KB |
Output is correct |
| 4 |
Correct |
93 ms |
173804 KB |
Output is correct |
| 5 |
Correct |
94 ms |
173824 KB |
Output is correct |
| 6 |
Correct |
92 ms |
173804 KB |
Output is correct |
| 7 |
Correct |
98 ms |
173804 KB |
Output is correct |
| 8 |
Correct |
93 ms |
173804 KB |
Output is correct |
| 9 |
Correct |
93 ms |
173804 KB |
Output is correct |
| 10 |
Correct |
93 ms |
173804 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
92 ms |
173804 KB |
Output is correct |
| 2 |
Correct |
93 ms |
173804 KB |
Output is correct |
| 3 |
Correct |
93 ms |
173804 KB |
Output is correct |
| 4 |
Correct |
93 ms |
173932 KB |
Output is correct |
| 5 |
Correct |
94 ms |
173804 KB |
Output is correct |
| 6 |
Correct |
94 ms |
173804 KB |
Output is correct |
| 7 |
Correct |
93 ms |
173784 KB |
Output is correct |
| 8 |
Correct |
93 ms |
173824 KB |
Output is correct |
| 9 |
Correct |
95 ms |
173804 KB |
Output is correct |
| 10 |
Correct |
92 ms |
173804 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
95 ms |
173964 KB |
Output is correct |
| 2 |
Correct |
95 ms |
173952 KB |
Output is correct |
| 3 |
Correct |
92 ms |
173804 KB |
Output is correct |
| 4 |
Correct |
93 ms |
173804 KB |
Output is correct |
| 5 |
Correct |
94 ms |
173824 KB |
Output is correct |
| 6 |
Correct |
92 ms |
173804 KB |
Output is correct |
| 7 |
Correct |
98 ms |
173804 KB |
Output is correct |
| 8 |
Correct |
93 ms |
173804 KB |
Output is correct |
| 9 |
Correct |
93 ms |
173804 KB |
Output is correct |
| 10 |
Correct |
93 ms |
173804 KB |
Output is correct |
| 11 |
Correct |
92 ms |
173804 KB |
Output is correct |
| 12 |
Correct |
93 ms |
173804 KB |
Output is correct |
| 13 |
Correct |
93 ms |
173804 KB |
Output is correct |
| 14 |
Correct |
93 ms |
173932 KB |
Output is correct |
| 15 |
Correct |
94 ms |
173804 KB |
Output is correct |
| 16 |
Correct |
94 ms |
173804 KB |
Output is correct |
| 17 |
Correct |
93 ms |
173784 KB |
Output is correct |
| 18 |
Correct |
93 ms |
173824 KB |
Output is correct |
| 19 |
Correct |
95 ms |
173804 KB |
Output is correct |
| 20 |
Correct |
92 ms |
173804 KB |
Output is correct |
| 21 |
Correct |
95 ms |
173804 KB |
Output is correct |
| 22 |
Correct |
350 ms |
174112 KB |
Output is correct |
| 23 |
Correct |
316 ms |
173804 KB |
Output is correct |
| 24 |
Correct |
282 ms |
173804 KB |
Output is correct |
| 25 |
Correct |
321 ms |
173932 KB |
Output is correct |
| 26 |
Correct |
268 ms |
173804 KB |
Output is correct |
| 27 |
Correct |
147 ms |
174060 KB |
Output is correct |
| 28 |
Correct |
173 ms |
173804 KB |
Output is correct |
| 29 |
Correct |
264 ms |
173864 KB |
Output is correct |
| 30 |
Correct |
324 ms |
173932 KB |
Output is correct |
