#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e9 + 7;
int n, L, a[101];
long long dp[101][101][1005][3];
signed main() {
cin >> n >> L;
for (int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + n + 1);
if(n == 1) {
cout << 1;
return 0;
}
dp[1][1][0][0] = 1;
dp[1][1][0][1] = 2;
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= i; ++j) {
for (int k = 0; k <= L; ++k) {
for (int e = 0; e < 3; ++e) {
if(dp[i][j][k][e] == 0) continue;
int new_cost = k + (a[i + 1] - a[i]) * (2 * j - e);
if(new_cost > L) continue;
(dp[i + 1][j + 1][new_cost][e] += dp[i][j][k][e] * (j + 1 - e)) %= Mod;
(dp[i + 1][j][new_cost][e] += dp[i][j][k][e] * (2 * j - e)) %= Mod;
(dp[i + 1][j - 1][new_cost][e] += dp[i][j][k][e] * (j - 1)) %= Mod;
if(e < 2) {
(dp[i + 1][j + 1][new_cost][e + 1] += dp[i][j][k][e] * (2 - e)) %= Mod;
(dp[i + 1][j][new_cost][e + 1] += dp[i][j][k][e] * (2 - e)) %= Mod;
}
}
}
}
}
long long ans = 0;
for (int i = 0; i <= L; ++i) {
ans += dp[n][1][i][2];
ans %= Mod;
}
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
2496 KB |
Output is correct |
3 |
Correct |
1 ms |
2392 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
1 ms |
2652 KB |
Output is correct |
7 |
Correct |
1 ms |
2652 KB |
Output is correct |
8 |
Correct |
1 ms |
2652 KB |
Output is correct |
9 |
Correct |
1 ms |
2648 KB |
Output is correct |
10 |
Correct |
1 ms |
2648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2908 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2904 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
2 ms |
2908 KB |
Output is correct |
7 |
Correct |
1 ms |
2652 KB |
Output is correct |
8 |
Correct |
1 ms |
2908 KB |
Output is correct |
9 |
Correct |
1 ms |
3164 KB |
Output is correct |
10 |
Correct |
2 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
2496 KB |
Output is correct |
3 |
Correct |
1 ms |
2392 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
1 ms |
2652 KB |
Output is correct |
7 |
Correct |
1 ms |
2652 KB |
Output is correct |
8 |
Correct |
1 ms |
2652 KB |
Output is correct |
9 |
Correct |
1 ms |
2648 KB |
Output is correct |
10 |
Correct |
1 ms |
2648 KB |
Output is correct |
11 |
Correct |
2 ms |
2908 KB |
Output is correct |
12 |
Correct |
1 ms |
2652 KB |
Output is correct |
13 |
Correct |
1 ms |
2904 KB |
Output is correct |
14 |
Correct |
1 ms |
2652 KB |
Output is correct |
15 |
Correct |
1 ms |
2652 KB |
Output is correct |
16 |
Correct |
2 ms |
2908 KB |
Output is correct |
17 |
Correct |
1 ms |
2652 KB |
Output is correct |
18 |
Correct |
1 ms |
2908 KB |
Output is correct |
19 |
Correct |
1 ms |
3164 KB |
Output is correct |
20 |
Correct |
2 ms |
2652 KB |
Output is correct |
21 |
Correct |
2 ms |
3672 KB |
Output is correct |
22 |
Correct |
34 ms |
28844 KB |
Output is correct |
23 |
Correct |
24 ms |
12636 KB |
Output is correct |
24 |
Correct |
25 ms |
16980 KB |
Output is correct |
25 |
Correct |
29 ms |
14508 KB |
Output is correct |
26 |
Correct |
23 ms |
13244 KB |
Output is correct |
27 |
Correct |
13 ms |
13404 KB |
Output is correct |
28 |
Correct |
16 ms |
15708 KB |
Output is correct |
29 |
Correct |
27 ms |
21324 KB |
Output is correct |
30 |
Correct |
27 ms |
14428 KB |
Output is correct |