#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#define debugArr(...) 69
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 100 + 23;
const int M = 1000 + 23;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
#define F first
#define S second
#define pb push_back
#define kill(x) cout<<x<<endl, exit(0);
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define lc (v << 1)
#define rc ((v<<1) |1)
#define int ll
void ok(int &x) {
if(x < 0) x += mod*mod;
x %= mod;
}
int n,l;
int a[N];
int dp[N][N][M][3];
int32_t main() {
cin.tie(nullptr)->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] = M*M;
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 ++) {
int cost = (2*j-m)*(a[i+1]-a[i]);
if(k-cost < 0 || i + j+ 1-m > n) continue;
// halat aval-> componente jadid:
ok(dp[i][j][k][m] += dp[i-1][j-1][k-cost][m]);
// halat dovom -> componente jadid az yeki az do sar
if(m)
ok(dp[i][j][k][m] += (3-m)*dp[i-1][j-1][k-cost][m-1]);
// halat sevom -> ezafe be tahe component
ok(dp[i][j][k][m] += (2 *j - m) * dp[i-1][j][k-cost][m]);
// halat 4:
if(m == 1) {
ok(dp[i][j][k][m] += 2*j * dp[i-1][j][k-cost][m-1]);
} else if(m == 2) {
if(i == n) {
ok(dp[i][j][k][m] += dp[i-1][j][k-cost][m-1]);
} else {
ok(dp[i][j][k][m] += (j-1)*dp[i-1][j][k-cost][m-1]);
}
}
// halat 5:
if(m == 2 && i == n) {
ok(dp[i][j][k][m] += dp[i-1][j+1][k-cost][m]);
} else if(m == 2) {
ok(dp[i][j][k][m] += j*(j-1)%mod*dp[i-1][j+1][k-cost][m]);
} else if(m == 1) {
ok(dp[i][j][k][m] += j*j%mod*dp[i-1][j+1][k-cost][m]);
} else {
ok(dp[i][j][k][m] += j*(j+1)%mod*dp[i-1][j+1][k-cost][m]);
}
}
int ans =0;
for(int i = 0 ; i <= l; i ++) ok(ans += dp[n][1][i][2]);
cout<<ans << '\n';
return 0;
}
// Jumpsuit, Jumpsuit cover me!
// Jumpsuit, Jumpsuit cover me!
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
600 KB |
Output is correct |
| 3 |
Correct |
0 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
1 ms |
600 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
1 ms |
728 KB |
Output is correct |
| 10 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
