#include <bits/stdc++.h>
using namespace std;
constexpr int NMAX = 105;
constexpr int LMAX = 1005;
constexpr int MOD = 1e9 + 7;
int N, L;
int a[NMAX];
void Read () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> L;
for (int i = 1; i <= N; ++ i )
cin >> a[i];
sort(a+1, a+N+1);
}
int dp[NMAX][NMAX][LMAX][2][2];
void Add (int &x, int y) {
x = (1LL * x + 1LL * y) % MOD;
}
void Solve () {
for (int S = 0; S < 2; ++ S )
for (int F = 0; F < 2; ++ F )
dp[1][0][0][S][F] = 1;
for (int i = 1; i < N; ++ i )
for (int cnt_space = 0; cnt_space <= N; ++ cnt_space)
for (int curr_sum = 0; curr_sum <= L; ++ curr_sum)
for (int S = 0; S < 2; ++ S )
for (int F = 0; F < 2; ++ F ) {
int new_sum = curr_sum + (a[i+1] - a[i]) * (2 * cnt_space + S + F);
if (new_sum > L) continue;
if (cnt_space > 0)
Add(dp[i+1][cnt_space-1][new_sum][S][F], (1LL * dp[i][cnt_space][curr_sum][S][F] * cnt_space) % MOD);
if (cnt_space < N)
Add(dp[i+1][cnt_space+1][new_sum][S][F], (1LL * dp[i][cnt_space][curr_sum][S][F] * cnt_space) % MOD);
Add(dp[i+1][cnt_space][new_sum][S][F], (1LL * dp[i][cnt_space][curr_sum][S][F] * 2 * cnt_space) % MOD);
if (S == 1) {
for (int aux_S = 0; aux_S < 2; ++ aux_S) {
Add(dp[i+1][cnt_space][new_sum][aux_S][F], dp[i][cnt_space][curr_sum][S][F]);
if (cnt_space < N)
Add(dp[i+1][cnt_space+1][new_sum][aux_S][F], dp[i][cnt_space][curr_sum][S][F]);
}
}
if (F == 1) {
for (int aux_F = 0; aux_F < 2; ++ aux_F) {
Add(dp[i+1][cnt_space][new_sum][S][aux_F], dp[i][cnt_space][curr_sum][S][F]);
if (cnt_space < N)
Add(dp[i+1][cnt_space+1][new_sum][S][aux_F], dp[i][cnt_space][curr_sum][S][F]);
}
}
}
int ans = 0;
for (int s = 0; s <= L; ++ s )
ans = (1LL * ans + dp[N][0][s][0][0]) % MOD;
cout << ans << '\n';
}
int main () {
Read();
Solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
320 KB |
Output is correct |
4 |
Correct |
1 ms |
464 KB |
Output is correct |
5 |
Correct |
2 ms |
848 KB |
Output is correct |
6 |
Correct |
3 ms |
848 KB |
Output is correct |
7 |
Correct |
1 ms |
592 KB |
Output is correct |
8 |
Correct |
1 ms |
592 KB |
Output is correct |
9 |
Correct |
3 ms |
976 KB |
Output is correct |
10 |
Correct |
1 ms |
592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
960 KB |
Output is correct |
2 |
Correct |
2 ms |
976 KB |
Output is correct |
3 |
Correct |
1 ms |
1104 KB |
Output is correct |
4 |
Correct |
2 ms |
976 KB |
Output is correct |
5 |
Correct |
1 ms |
976 KB |
Output is correct |
6 |
Correct |
2 ms |
1104 KB |
Output is correct |
7 |
Correct |
1 ms |
848 KB |
Output is correct |
8 |
Correct |
1 ms |
1188 KB |
Output is correct |
9 |
Correct |
2 ms |
1232 KB |
Output is correct |
10 |
Correct |
1 ms |
976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
320 KB |
Output is correct |
4 |
Correct |
1 ms |
464 KB |
Output is correct |
5 |
Correct |
2 ms |
848 KB |
Output is correct |
6 |
Correct |
3 ms |
848 KB |
Output is correct |
7 |
Correct |
1 ms |
592 KB |
Output is correct |
8 |
Correct |
1 ms |
592 KB |
Output is correct |
9 |
Correct |
3 ms |
976 KB |
Output is correct |
10 |
Correct |
1 ms |
592 KB |
Output is correct |
11 |
Correct |
2 ms |
960 KB |
Output is correct |
12 |
Correct |
2 ms |
976 KB |
Output is correct |
13 |
Correct |
1 ms |
1104 KB |
Output is correct |
14 |
Correct |
2 ms |
976 KB |
Output is correct |
15 |
Correct |
1 ms |
976 KB |
Output is correct |
16 |
Correct |
2 ms |
1104 KB |
Output is correct |
17 |
Correct |
1 ms |
848 KB |
Output is correct |
18 |
Correct |
1 ms |
1188 KB |
Output is correct |
19 |
Correct |
2 ms |
1232 KB |
Output is correct |
20 |
Correct |
1 ms |
976 KB |
Output is correct |
21 |
Correct |
4 ms |
3920 KB |
Output is correct |
22 |
Correct |
393 ms |
92308 KB |
Output is correct |
23 |
Correct |
402 ms |
86508 KB |
Output is correct |
24 |
Correct |
378 ms |
93528 KB |
Output is correct |
25 |
Correct |
409 ms |
89012 KB |
Output is correct |
26 |
Correct |
365 ms |
84912 KB |
Output is correct |
27 |
Correct |
153 ms |
63436 KB |
Output is correct |
28 |
Correct |
199 ms |
72100 KB |
Output is correct |
29 |
Correct |
368 ms |
99240 KB |
Output is correct |
30 |
Correct |
416 ms |
87988 KB |
Output is correct |