#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define int long long
#define nl '\n'
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1000000007, mod2 = 998244353;
// change this
const int N = 105;
const int L = 1005;
int n, l, arr[N], dp[N][N][L][3];
signed main() {
io;
cin >> n >> l;
for (int i=1; i<=n; i++) cin >> arr[i];
if (n == 1) {
cout << 1 << nl;
return 0;
}
sort(arr, arr+n+1);
arr[n+1] = 1e9;
dp[0][0][0][0] = 1;
for (int i=1; i<=n; i++) {
for (int j=1; j<=i; j++) {
for (int k=0; k<=l; k++) {
for (int m=0; m<3; m++) {
// i: index, j: components, k: sum, m: ends
int dc = (2*j-m) * (arr[i+1] - arr[i]);
// difference in cost. each component contributes 2*j except for the m ones which contribute 1
if (dc > k) continue; // cost too much lol
// we can create a new component that isn't the end
dp[i][j][k][m] += dp[i-1][j-1][k-dc][m];
// we can create a new component that is the end
if (m) dp[i][j][k][m] += (3-m) * dp[i-1][j-1][k-dc][m-1];
// we can join an existing component but not combine
dp[i][j][k][m] += (2*j-m) * dp[i-1][j][k-dc][m];
// we can join two existing components [[...]X[...]]
if (m == 0) {
dp[i][j][k][m] += j*(j+1)*dp[i-1][j+1][k-dc][m];
// for each of the j+1 i can match with j
} else if (m == 1) {
dp[i][j][k][m] += j*j*dp[i-1][j+1][k-dc][m];
// for each of the j (because end cannot) i can match with j
} else {
if (i == n) dp[i][j][k][m] += dp[i-1][j+1][k-dc][m];
else dp[i][j][k][m] += j*(j-1)*dp[i-1][j+1][k-dc][m];
// for each of the j-1 (because ends cannot) i can match with j
}
// we can bring an existing component to the end
if (m == 1) {
dp[i][j][k][m] += (2*j) * dp[i-1][j][k-dc][m-1]; // 2j components to select from (two ends of each)
} else if (m == 2) {
if (i == n) dp[i][j][k][m] += dp[i-1][j][k-dc][m-1]; // only one thing to select from
else if (j) dp[i][j][k][m] += (j-1) * dp[i-1][j][k-dc][m-1]; // j-1 components to select from (one end of each except other end)
}
dp[i][j][k][m] %= mod;
}
}
}
}
int ans = 0;
for (int i=0; i<=l; i++) {
ans += dp[n][1][i][2];
ans %= mod;
}
cout << ans << nl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
492 KB |
Output is correct |
5 |
Correct |
1 ms |
876 KB |
Output is correct |
6 |
Correct |
1 ms |
748 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
2 ms |
876 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
748 KB |
Output is correct |
2 |
Correct |
1 ms |
748 KB |
Output is correct |
3 |
Correct |
1 ms |
876 KB |
Output is correct |
4 |
Correct |
1 ms |
748 KB |
Output is correct |
5 |
Correct |
1 ms |
748 KB |
Output is correct |
6 |
Correct |
1 ms |
876 KB |
Output is correct |
7 |
Correct |
1 ms |
748 KB |
Output is correct |
8 |
Correct |
1 ms |
876 KB |
Output is correct |
9 |
Correct |
1 ms |
876 KB |
Output is correct |
10 |
Correct |
1 ms |
748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
492 KB |
Output is correct |
5 |
Correct |
1 ms |
876 KB |
Output is correct |
6 |
Correct |
1 ms |
748 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
2 ms |
876 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
748 KB |
Output is correct |
12 |
Correct |
1 ms |
748 KB |
Output is correct |
13 |
Correct |
1 ms |
876 KB |
Output is correct |
14 |
Correct |
1 ms |
748 KB |
Output is correct |
15 |
Correct |
1 ms |
748 KB |
Output is correct |
16 |
Correct |
1 ms |
876 KB |
Output is correct |
17 |
Correct |
1 ms |
748 KB |
Output is correct |
18 |
Correct |
1 ms |
876 KB |
Output is correct |
19 |
Correct |
1 ms |
876 KB |
Output is correct |
20 |
Correct |
1 ms |
748 KB |
Output is correct |
21 |
Correct |
3 ms |
3180 KB |
Output is correct |
22 |
Correct |
88 ms |
65516 KB |
Output is correct |
23 |
Correct |
97 ms |
76396 KB |
Output is correct |
24 |
Correct |
92 ms |
74988 KB |
Output is correct |
25 |
Correct |
99 ms |
77036 KB |
Output is correct |
26 |
Correct |
93 ms |
71788 KB |
Output is correct |
27 |
Correct |
44 ms |
41324 KB |
Output is correct |
28 |
Correct |
52 ms |
47852 KB |
Output is correct |
29 |
Correct |
87 ms |
72776 KB |
Output is correct |
30 |
Correct |
100 ms |
77292 KB |
Output is correct |