#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME (1.0 * clock() / CLOCKS_PER_SEC)
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 1e6 + 5;
const int oo = 1e9, mod = 1e9 + 7;
int n, m, k, r[55], l, pas[10055][10055], x=0, dp[3][55][10005];
int mul(int a, int b) {
return (int)a*b%mod;
}
int add(int a, int b) {
return (int)(a+b)%mod;
}
void pascal() {
foru(i,0,l+n) pas[i][0]=1;
foru(i,1,l) {
foru(j,1,min(n,i)) {
pas[i][j]=add(pas[i-1][j], pas[i-1][j-1]);
}
}
return;
}
void process() {
cin >> n >> l;
foru(i,1,n) cin >> r[i];
sort(r+1, r+1+n);
pascal();
int x=0;
dp[0][0][0]=1;
foru(i,1,n) {
x^=1;
dp[x][0][0]=0;
int R=r[i];
foru(j,1,i) {
foru(k,1,l) {
dp[x][j][k]=dp[!x][j-1][k-1];
if (k>=R) dp[x][j][k]=add(dp[x][j][k], mul(dp[!x][j][k-R], 2*j));
if (k>=2*R-1) dp[x][j][k]=add(dp[x][j][k], mul(dp[!x][j+1][k-2*R+1], j*(j+1)));
}
}
}
int sol=0;
foru(i,1,l) sol=add(sol, mul(dp[x][1][i], pas[l-i+n][n]));
cout << sol;
return;
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
//freopen(".inp", "r", stdin);
//freopen(".out", "w", stdout);
process();
//cerr << "Time elapsed: " << __TIME << " s.\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
127 ms |
366932 KB |
Output is correct |
2 |
Correct |
2 ms |
12888 KB |
Output is correct |
3 |
Correct |
44 ms |
353432 KB |
Output is correct |
4 |
Correct |
42 ms |
358480 KB |
Output is correct |
5 |
Correct |
28 ms |
238932 KB |
Output is correct |
6 |
Correct |
66 ms |
360372 KB |
Output is correct |
7 |
Correct |
53 ms |
346448 KB |
Output is correct |
8 |
Correct |
21 ms |
199248 KB |
Output is correct |
9 |
Correct |
40 ms |
339028 KB |
Output is correct |
10 |
Correct |
24 ms |
246612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
360820 KB |
Output is correct |
2 |
Correct |
36 ms |
339776 KB |
Output is correct |
3 |
Correct |
47 ms |
358844 KB |
Output is correct |
4 |
Correct |
40 ms |
347624 KB |
Output is correct |
5 |
Correct |
45 ms |
356944 KB |
Output is correct |
6 |
Correct |
34 ms |
333908 KB |
Output is correct |
7 |
Correct |
48 ms |
356948 KB |
Output is correct |
8 |
Correct |
8 ms |
76380 KB |
Output is correct |
9 |
Correct |
36 ms |
331612 KB |
Output is correct |
10 |
Correct |
35 ms |
330068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
29276 KB |
Output is correct |
2 |
Correct |
3 ms |
23128 KB |
Output is correct |
3 |
Correct |
4 ms |
29176 KB |
Output is correct |
4 |
Correct |
4 ms |
29276 KB |
Output is correct |
5 |
Correct |
4 ms |
29276 KB |
Output is correct |
6 |
Correct |
1 ms |
8540 KB |
Output is correct |
7 |
Correct |
4 ms |
29276 KB |
Output is correct |
8 |
Correct |
3 ms |
26972 KB |
Output is correct |
9 |
Correct |
3 ms |
25180 KB |
Output is correct |
10 |
Correct |
3 ms |
24924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
127 ms |
366932 KB |
Output is correct |
2 |
Correct |
2 ms |
12888 KB |
Output is correct |
3 |
Correct |
44 ms |
353432 KB |
Output is correct |
4 |
Correct |
42 ms |
358480 KB |
Output is correct |
5 |
Correct |
28 ms |
238932 KB |
Output is correct |
6 |
Correct |
66 ms |
360372 KB |
Output is correct |
7 |
Correct |
53 ms |
346448 KB |
Output is correct |
8 |
Correct |
21 ms |
199248 KB |
Output is correct |
9 |
Correct |
40 ms |
339028 KB |
Output is correct |
10 |
Correct |
24 ms |
246612 KB |
Output is correct |
11 |
Correct |
48 ms |
360820 KB |
Output is correct |
12 |
Correct |
36 ms |
339776 KB |
Output is correct |
13 |
Correct |
47 ms |
358844 KB |
Output is correct |
14 |
Correct |
40 ms |
347624 KB |
Output is correct |
15 |
Correct |
45 ms |
356944 KB |
Output is correct |
16 |
Correct |
34 ms |
333908 KB |
Output is correct |
17 |
Correct |
48 ms |
356948 KB |
Output is correct |
18 |
Correct |
8 ms |
76380 KB |
Output is correct |
19 |
Correct |
36 ms |
331612 KB |
Output is correct |
20 |
Correct |
35 ms |
330068 KB |
Output is correct |
21 |
Correct |
4 ms |
29276 KB |
Output is correct |
22 |
Correct |
3 ms |
23128 KB |
Output is correct |
23 |
Correct |
4 ms |
29176 KB |
Output is correct |
24 |
Correct |
4 ms |
29276 KB |
Output is correct |
25 |
Correct |
4 ms |
29276 KB |
Output is correct |
26 |
Correct |
1 ms |
8540 KB |
Output is correct |
27 |
Correct |
4 ms |
29276 KB |
Output is correct |
28 |
Correct |
3 ms |
26972 KB |
Output is correct |
29 |
Correct |
3 ms |
25180 KB |
Output is correct |
30 |
Correct |
3 ms |
24924 KB |
Output is correct |
31 |
Correct |
129 ms |
367052 KB |
Output is correct |
32 |
Correct |
89 ms |
349824 KB |
Output is correct |
33 |
Correct |
127 ms |
363104 KB |
Output is correct |
34 |
Correct |
55 ms |
349284 KB |
Output is correct |
35 |
Correct |
124 ms |
366932 KB |
Output is correct |
36 |
Correct |
43 ms |
347984 KB |
Output is correct |
37 |
Correct |
129 ms |
365272 KB |
Output is correct |
38 |
Correct |
28 ms |
143184 KB |
Output is correct |
39 |
Correct |
124 ms |
365140 KB |
Output is correct |
40 |
Correct |
66 ms |
357200 KB |
Output is correct |
41 |
Correct |
127 ms |
365392 KB |
Output is correct |
42 |
Correct |
19 ms |
183132 KB |
Output is correct |
43 |
Correct |
124 ms |
365140 KB |
Output is correct |
44 |
Correct |
44 ms |
344912 KB |
Output is correct |
45 |
Correct |
124 ms |
366900 KB |
Output is correct |
46 |
Correct |
40 ms |
355132 KB |
Output is correct |
47 |
Correct |
50 ms |
351472 KB |
Output is correct |
48 |
Correct |
23 ms |
186192 KB |
Output is correct |
49 |
Correct |
40 ms |
348752 KB |
Output is correct |
50 |
Correct |
4 ms |
33368 KB |
Output is correct |