/* Bismillahir Rahmanir Rahim */
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int L = 1005;
const long long mod = 1e9 + 7;
long long dp[N][L][N][2][2];
int n, l, a[N];
long long recur(int at, int sum, int tot, int lf, int rf){
int fuk = sum + ((a[at] - a[at-1]) * (lf + rf + tot * 2));
if(fuk > l || tot < 0) return 0;
if(at == n) return (tot == 0);
if(dp[at][sum][tot][lf][rf] != -1) return dp[at][sum][tot][lf][rf];
long long ret = 0;
ret += recur(at+1, fuk, tot, 1, rf);
ret += recur(at+1, fuk, tot-1, 1, rf) * tot;
ret += recur(at+1, fuk, tot, lf, 1);
ret += recur(at+1, fuk, tot-1, lf, 1) * tot;
ret += recur(at+1, fuk, tot, lf, rf) * tot * 2;
ret += recur(at+1, fuk, tot-1, lf, rf) * tot * (tot - 1);
ret += recur(at+1, fuk, tot+1, lf, rf);
return dp[at][sum][tot][lf][rf] = ret % mod;
}
int main(){
cin >> n >> l;
for(int i=1;i<=n;i++){
cin >> a[i];
}
sort(a+1, a+1+n); a[0] = a[1];
memset(dp, -1, sizeof(dp));
cout << recur(1, 0, 0, 0, 0) << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
348272 KB |
Output is correct |
| 2 |
Correct |
26 ms |
348272 KB |
Output is correct |
| 3 |
Correct |
23 ms |
348272 KB |
Output is correct |
| 4 |
Correct |
26 ms |
348272 KB |
Output is correct |
| 5 |
Correct |
36 ms |
348272 KB |
Output is correct |
| 6 |
Correct |
43 ms |
348272 KB |
Output is correct |
| 7 |
Correct |
36 ms |
348272 KB |
Output is correct |
| 8 |
Correct |
39 ms |
348272 KB |
Output is correct |
| 9 |
Correct |
39 ms |
348272 KB |
Output is correct |
| 10 |
Correct |
16 ms |
348272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
348272 KB |
Output is correct |
| 2 |
Correct |
23 ms |
348272 KB |
Output is correct |
| 3 |
Correct |
26 ms |
348272 KB |
Output is correct |
| 4 |
Correct |
13 ms |
348272 KB |
Output is correct |
| 5 |
Correct |
13 ms |
348272 KB |
Output is correct |
| 6 |
Correct |
36 ms |
348272 KB |
Output is correct |
| 7 |
Correct |
9 ms |
348272 KB |
Output is correct |
| 8 |
Correct |
23 ms |
348272 KB |
Output is correct |
| 9 |
Correct |
16 ms |
348272 KB |
Output is correct |
| 10 |
Correct |
23 ms |
348272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
348272 KB |
Output is correct |
| 2 |
Correct |
26 ms |
348272 KB |
Output is correct |
| 3 |
Correct |
23 ms |
348272 KB |
Output is correct |
| 4 |
Correct |
26 ms |
348272 KB |
Output is correct |
| 5 |
Correct |
36 ms |
348272 KB |
Output is correct |
| 6 |
Correct |
43 ms |
348272 KB |
Output is correct |
| 7 |
Correct |
36 ms |
348272 KB |
Output is correct |
| 8 |
Correct |
39 ms |
348272 KB |
Output is correct |
| 9 |
Correct |
39 ms |
348272 KB |
Output is correct |
| 10 |
Correct |
16 ms |
348272 KB |
Output is correct |
| 11 |
Correct |
49 ms |
348272 KB |
Output is correct |
| 12 |
Correct |
23 ms |
348272 KB |
Output is correct |
| 13 |
Correct |
26 ms |
348272 KB |
Output is correct |
| 14 |
Correct |
13 ms |
348272 KB |
Output is correct |
| 15 |
Correct |
13 ms |
348272 KB |
Output is correct |
| 16 |
Correct |
36 ms |
348272 KB |
Output is correct |
| 17 |
Correct |
9 ms |
348272 KB |
Output is correct |
| 18 |
Correct |
23 ms |
348272 KB |
Output is correct |
| 19 |
Correct |
16 ms |
348272 KB |
Output is correct |
| 20 |
Correct |
23 ms |
348272 KB |
Output is correct |
| 21 |
Correct |
9 ms |
348272 KB |
Output is correct |
| 22 |
Correct |
303 ms |
348272 KB |
Output is correct |
| 23 |
Correct |
209 ms |
348272 KB |
Output is correct |
| 24 |
Correct |
216 ms |
348272 KB |
Output is correct |
| 25 |
Correct |
206 ms |
348272 KB |
Output is correct |
| 26 |
Correct |
213 ms |
348272 KB |
Output is correct |
| 27 |
Correct |
76 ms |
348272 KB |
Output is correct |
| 28 |
Correct |
103 ms |
348272 KB |
Output is correct |
| 29 |
Correct |
196 ms |
348272 KB |
Output is correct |
| 30 |
Correct |
229 ms |
348272 KB |
Output is correct |
