#include <bits/stdc++.h>
using namespace std;
inline namespace
{
} // namespace
const long MOD = 1'000'000'007;
void solve()
{
int n;
int l;
cin >> n >> l;
vector<int> a(n);
for (int &x : a)
cin >> x;
sort(a.begin(), a.end());
vector dp(1, vector(l + 1, vector<long>(3, 0)));
dp[0][0][0] = 1;
for (int i = 0; i < n - 1; i++)
{
vector nxt_dp(i + 2, vector(l + 1, vector<long>(3, 0)));
for (int j = 1; j <= i + 1; j++)
{
for (int x = 0; x <= l; x++)
{
for (int k = 0; k <= 2; k++)
{
long cost = (2 * j - k) * (a[i + 1] - a[i]);
if (x >= cost)
{
// create new component w/o endpoint
nxt_dp[j][x][k] += (j - k) * dp[j - 1][x - cost][k];
// create new component w/ endpoint
if (k >= 1)
nxt_dp[j][x][k] += (3 - k) * dp[j - 1][x - cost][k - 1];
if (j <= i)
{
// add to component w/o endpoint
nxt_dp[j][x][k] += (2 * j - k) * dp[j][x - cost][k];
// add to component w/ endpoint
if (k >= 1)
nxt_dp[j][x][k] += (3 - k) * dp[j][x - cost][k - 1];
}
if (j < i)
// merge two components
nxt_dp[j][x][k] += j * dp[j + 1][x - cost][k];
nxt_dp[j][x][k] %= MOD;
}
}
}
}
dp = move(nxt_dp);
}
long cnt = 0;
for (int x = 0; x <= l; x++)
cnt += dp[1][x][1] + dp[2][x][2];
cnt %= MOD;
cout << cnt << '\n';
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(NULL);
solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
352 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
444 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
320 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |