#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MXN = 105;
const int MXL = 1005;
const int INF = 1e5 + 5;
const int MOD = 1e9 + 7;
int n, L, a[MXN];
ll dp[MXN][MXN][MXL][2][2];
int32_t main() {
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);
cin >> n >> L;
for(int i=1; i<=n; i++) cin >> a[i];
sort(a+1, a+n+1);
a[n+1] = INF;
dp[1][1][0][0][0] = 1;
if(a[2]-a[1]<=L) dp[1][1][a[2]-a[1]][0][1] = dp[1][1][a[2]-a[1]][1][0] = 1;
if((a[2]-a[1])*2<=L) dp[1][1][(a[2]-a[1])<<1][1][1] = 1;
for(int i=1; i<n; i++)
for(int j=1; j<=i; j++)
for(int k=0; k<=L; k++)
for(int b1 : {0, 1})
for(int b2 : {0, 1}) {
if(b1) {
int kk = k + (2*(j-1)+b1+b2)*(a[i+2]-a[i+1]);
if(kk<=L) (dp[i+1][j][kk][b1][b2] += dp[i][j][k][b1][b2]) %= MOD;
kk = k + (2*(j-1)+b2)*(a[i+2]-a[i+1]);
if(kk<=L) (dp[i+1][j][kk][0][b2] += dp[i][j][k][b1][b2]) %= MOD;
kk = k + (2*j+b1+b2)*(a[i+2]-a[i+1]);
if(kk<=L) (dp[i+1][j+1][kk][b1][b2] += dp[i][j][k][b1][b2]) %= MOD;
kk = k + (2*j+b2)*(a[i+2]-a[i+1]);
if(kk<=L) (dp[i+1][j+1][kk][0][b2] += dp[i][j][k][b1][b2]) %= MOD;
}
if(b2) {
int kk = k + (2*(j-1)+b1+b2)*(a[i+2]-a[i+1]);
if(kk<=L) (dp[i+1][j][kk][b1][b2] += dp[i][j][k][b1][b2]) %= MOD;
kk = k + (2*(j-1)+b1)*(a[i+2]-a[i+1]);
if(kk<=L) (dp[i+1][j][kk][b1][0] += dp[i][j][k][b1][b2]) %= MOD;
kk = k + (2*j+b1+b2)*(a[i+2]-a[i+1]);
if(kk<=L) (dp[i+1][j+1][kk][b1][b2] += dp[i][j][k][b1][b2]) %= MOD;
kk = k + (2*j+b1)*(a[i+2]-a[i+1]);
if(kk<=L) (dp[i+1][j+1][kk][b1][0] += dp[i][j][k][b1][b2]) %= MOD;
}
if(j>1) {
int kk = k + (2*(j-1)+b1+b2)*(a[i+2]-a[i+1]);
if(kk<=L) (dp[i+1][j][kk][b1][b2] += 2*(j-1)*dp[i][j][k][b1][b2]) %= MOD;
kk = k + (2*j+b1+b2)*(a[i+2]-a[i+1]);
if(kk<=L) (dp[i+1][j+1][kk][b1][b2] += (j-1)*dp[i][j][k][b1][b2]) %= MOD;
kk = k + (2*(j-2)+b1+b2)*(a[i+2]-a[i+1]);
if(kk<=L) (dp[i+1][j-1][kk][b1][b2] += (j-1)*dp[i][j][k][b1][b2]) %= MOD;
}
}
ll ans = 0;
for(int i=0; i<=L; i++)
(ans += dp[n][1][i][0][0]) %= MOD;
cout << ans << '\n';
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2908 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 |
2652 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2908 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2652 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2904 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3160 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2904 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2908 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2908 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 |
2652 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2908 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2904 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 14 |
Correct |
2 ms |
3160 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2904 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 20 |
Correct |
2 ms |
2908 KB |
Output is correct |
| 21 |
Correct |
3 ms |
5464 KB |
Output is correct |
| 22 |
Correct |
213 ms |
85332 KB |
Output is correct |
| 23 |
Correct |
278 ms |
100176 KB |
Output is correct |
| 24 |
Correct |
242 ms |
95680 KB |
Output is correct |
| 25 |
Correct |
297 ms |
101172 KB |
Output is correct |
| 26 |
Correct |
262 ms |
92240 KB |
Output is correct |
| 27 |
Correct |
94 ms |
50512 KB |
Output is correct |
| 28 |
Correct |
130 ms |
59100 KB |
Output is correct |
| 29 |
Correct |
210 ms |
92240 KB |
Output is correct |
| 30 |
Correct |
292 ms |
101460 KB |
Output is correct |
