#include <bits/stdc++.h>
//connected components dp practice
using namespace std;
const long long MOD = 1000000007LL;
void add(long long& x, long long y){
x += y;
if(x >= MOD) x -= MOD;
}
long long mul(long long a, long long b){
return (a*b + MOD)%MOD;
}
//# of ways for n (mod 2), # of components, L, # of ends used(0, 1, or 2)
long long dp[2][101][1001][3];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, L;
cin >> n >> L;
vector<int> array(n);
for(int k = 0; k < n; k++){
cin >> array[k];
}
sort(array.begin(),array.end());
if(n == 1){
cout << 1 << endl;
return 0;
}
if(n == 2){
if(array[1] - array[0] <= L){
cout << 2 << endl;
} else {
cout << 0 << endl;
}
return 0;
}
//n >= 3
//add first element in middle
dp[0][1][0][0] = 1LL;
//add on either end
dp[0][1][0][1] = 2LL;
int newcost;
for(int k = 0; k < n-1; k++){
int from = k&1;
int to = from^1;
int diff = array[k+1] - array[k];
for(int j = 1; j <= n; j++){
long long jl = (long long)j;
for(int h = 0; h <= L; h++){
//# of ends used
for(int g = 0; g <= 2; g++){
newcost = h + diff * (j*2 - g);
if(newcost <= L){
//add new component
if(j+1 <= n){
//add to middle (not an end)
add(dp[to][j+1][newcost][g], mul(dp[from][j][h][g],jl+1 - g));
//add to end
if(g == 0){
//2 ends open, add once for each end
add(dp[to][j+1][newcost][1], dp[from][j][h][0]);
add(dp[to][j+1][newcost][1], dp[from][j][h][0]);
} else if(g == 1){
//1 end open
add(dp[to][j+1][newcost][2], dp[from][j][h][1]);
}
}
//add to endpoint of component
//add to middle (not an end)
add(dp[to][j][newcost][g], mul(dp[from][j][h][g], jl*2LL - g));
//add to end
if(g == 0){
//2 ends open
add(dp[to][j][newcost][1], dp[from][j][h][0]);
add(dp[to][j][newcost][1], dp[from][j][h][0]);
} else if(g == 1){
//1 end open
add(dp[to][j][newcost][2], dp[from][j][h][1]);
}
//join components
if(j >= 2){
add(dp[to][j-1][newcost][g], mul(dp[from][j][h][g], jl-1));
}
}
//clear
dp[from][j][h][g] = 0LL;
}
}
}
}
long long answer = 0LL;
for(int l = 0; l <= L; l++){
add(answer,dp[n&1^1][1][l][2]);
}
cout << answer << endl;
return 0;
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:116:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
116 | add(answer,dp[n&1^1][1][l][2]);
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
1 ms |
2652 KB |
Output is correct |
7 |
Correct |
1 ms |
2512 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
2652 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 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 |
2392 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
1 ms |
2652 KB |
Output is correct |
7 |
Correct |
1 ms |
2512 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
2652 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
2652 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
2392 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
856 KB |
Output is correct |
22 |
Correct |
115 ms |
4088 KB |
Output is correct |
23 |
Correct |
120 ms |
5148 KB |
Output is correct |
24 |
Correct |
109 ms |
4700 KB |
Output is correct |
25 |
Correct |
123 ms |
5140 KB |
Output is correct |
26 |
Correct |
114 ms |
4956 KB |
Output is correct |
27 |
Correct |
40 ms |
2392 KB |
Output is correct |
28 |
Correct |
54 ms |
2652 KB |
Output is correct |
29 |
Correct |
104 ms |
3932 KB |
Output is correct |
30 |
Correct |
124 ms |
4952 KB |
Output is correct |