#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
const int N = 105, V = 1005;
const int M = 1e9 + 7;
LL dp[N][N][V][2][2], a[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, L;
cin >> n >> L;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n), a[n + 1] = V * 2;
int d = a[2] - a[1];
dp[1][1][0][0][0] = 1, dp[1][1][d][1][0] = 1;
dp[1][1][d][0][1] = 1, dp[1][1][d * 2][1][1] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= i; j++) {
for(int sum = 0; sum <= L; sum++) {
for(int l = 0; l <= 1; l++) {
for(int r = 0; r <= 1; r++) {
// place a new component in the middle
int new_sum = sum + (j * 2 + l + r) * (a[i + 2] - a[i + 1]);
dp[i + 1][j + 1][new_sum][l][r] += dp[i][j][sum][l][r] * (j - 1) % M;
dp[i + 1][j + 1][new_sum][l][r] %= M;
//place a new component in the left , don't block it
if(l > 0){
new_sum = sum + (j * 2 + l + r) * (a[i + 2] - a[i + 1]);
dp[i + 1][j + 1][new_sum][l][r] += dp[i][j][sum][l][r];
dp[i + 1][j + 1][new_sum][l][r] %= M;
}
//place a new component in the left and block it
if(l > 0){
new_sum = sum + (j * 2 + r) * (a[i + 2] - a[i + 1]);
dp[i + 1][j + 1][new_sum][0][r] += dp[i][j][sum][l][r];
dp[i + 1][j + 1][new_sum][0][r] %= M;
}
//place a new component in the right, don't block it
if(r > 0){
new_sum = sum + (j * 2 + l + r) * (a[i + 2] - a[i + 1]);
dp[i + 1][j + 1][new_sum][l][r] += dp[i][j][sum][l][r];
dp[i + 1][j + 1][new_sum][l][r] %= M;
}
//place a new component in the right and block it
if(r > 0){
new_sum = sum + (j * 2 + l) * (a[i + 2] - a[i + 1]);
dp[i + 1][j + 1][new_sum][l][0] += dp[i][j][sum][l][r];
dp[i + 1][j + 1][new_sum][l][0] %= M;
}
//add to existing component but not at the end of permutation
new_sum = sum + ((j - 1) * 2 + l + r) * (a[i + 2] - a[i + 1]);
dp[i + 1][j][new_sum][l][r] += dp[i][j][sum][l][r] * (j - 1 ) * 2 % M;
dp[i + 1][j][new_sum][l][r] %= M;
//adding to left of the leftmost component but do not block it
if(l > 0){
new_sum = sum + ((j - 1) * 2 + l + r) * (a[i + 2] - a[i + 1]);
dp[i + 1][j][new_sum][l][r] += dp[i][j][sum][l][r];
dp[i + 1][j][new_sum][l][r] %= M;
}
//adding to left of the leftmost component and block it
if(l > 0){
new_sum = sum + ((j - 1) * 2 + l + r - 1) * (a[i + 2] - a[i + 1]);
dp[i + 1][j][new_sum][0][r] += dp[i][j][sum][l][r];
dp[i + 1][j][new_sum][0][r] %= M;
}
//adding to right of the rightmost component but do not block it
if(r > 0){
new_sum = sum + ((j - 1) * 2 + l + r) * (a[i + 2] - a[i + 1]);
dp[i + 1][j][new_sum][l][r] += dp[i][j][sum][l][r];
dp[i + 1][j][new_sum][l][r] %= M;
}
//adding to right of the rightmost component and block it
if(r > 0){
new_sum = sum + ((j - 1) * 2 + l + r - 1) * (a[i + 2] - a[i + 1]);
dp[i + 1][j][new_sum][l][0] += dp[i][j][sum][l][r];
dp[i + 1][j][new_sum][l][0] %= M;
}
//merging two components
if(j > 1 ) {
new_sum = sum + ((j - 2 ) * 2 + l + r) * (a[i + 2] - a[i + 1]);
dp[i + 1][j - 1][new_sum][l][r] += dp[i][j][sum][l][r] * (j - 1)%M;
dp[i + 1][j - 1][new_sum][l][r] %= M;
}
}
}
}
}
}
LL ans = 0;
for(int sum = 0; sum <= L; sum++) ans = (ans + dp[n][1][sum][0][0]) % M;
cout << ans <<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
4956 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3676 KB |
Output is correct |
| 3 |
Correct |
1 ms |
3416 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3672 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3676 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3676 KB |
Output is correct |
| 7 |
Correct |
1 ms |
3420 KB |
Output is correct |
| 8 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 9 |
Correct |
2 ms |
3688 KB |
Output is correct |
| 10 |
Correct |
2 ms |
3676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
4956 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
