#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MOD = 1e9 + 7;
const int NMAX = 1e2;
const int LMAX = 1e3;
int n,l;
int v[NMAX + 5];
int dp[2][NMAX + 5][LMAX + 5][3];
void add_to(int a,int j,int k,int e,int val){
/// printf("to %d %d %d %d %d\n",a,j,k,e,val);
if(a < 0 || a > 1)return ;
if(j < 0 || j > n)return ;
if(k < 0 || k > l)return ;
if(e < 0 || e > 2)return ;
dp[a][j][k][e] += val;
dp[a][j][k][e] %= MOD;
}
int main(){
scanf("%d %d",&n,&l);
for(int i = 1;i <= n;i++){
scanf("%d",&v[i]);
}
sort(v + 1,v + 1 + n);
dp[1][0][0][0] = 1;
dp[1][0][0][1] = 2;
dp[1][0][0][2] = 1;
for(int i = 1,a = 1;i < n;i++,a ^= 1){
memset(dp[1 ^ a],0,sizeof(dp[1 ^ a]));
// if(i == 2)printf("%d\n",dp[a][0][2][1]);
for(int j = 0;j <= n;j++){
for(int k = 0;k <= l;k++){
for(int e = 0;e < 3;e++){
if(dp[a][j][k][e] == 0){
continue;
}
int cost = (v[i + 1] - v[i]) * (2 * j + e);
/// printf("from %d %d %d %d\n",a,j,k,e);
add_to(a ^ 1,j + 1,k + cost,e,1LL * dp[a][j][k][e] * j % MOD);
add_to(a ^ 1,j,k + cost,e,2LL * dp[a][j][k][e] * j % MOD);
add_to(a ^ 1,j - 1,k + cost,e,1LL * dp[a][j][k][e] * j % MOD);
add_to(a ^ 1,j + 1,k + cost,e,1LL * dp[a][j][k][e] * e % MOD);
add_to(a ^ 1,j,k + cost,e,1LL * dp[a][j][k][e] * e % MOD);
add_to(a ^ 1,j + 1,k + cost,e - 1,1LL * dp[a][j][k][e] * e % MOD);
add_to(a ^ 1,j,k + cost,e - 1,1LL * dp[a][j][k][e] * e % MOD);
}
}
}
}
int ans = 0;
for(int k = 0;k <= l;k++){
ans += dp[n & 1][0][k][0];
ans %= MOD;
}
printf("%d\n",ans);
return 0;
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&l);
~~~~~^~~~~~~~~~~~~~~
skyscraper.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&v[i]);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1528 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 5 |
Correct |
5 ms |
2912 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 9 |
Correct |
5 ms |
2812 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2936 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 5 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 6 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2780 KB |
Output is correct |
| 8 |
Correct |
14 ms |
2780 KB |
Output is correct |
| 9 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 10 |
Correct |
5 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1528 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 5 |
Correct |
5 ms |
2912 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 9 |
Correct |
5 ms |
2812 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 11 |
Correct |
5 ms |
2936 KB |
Output is correct |
| 12 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 13 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 14 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 15 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 16 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 17 |
Correct |
5 ms |
2780 KB |
Output is correct |
| 18 |
Correct |
14 ms |
2780 KB |
Output is correct |
| 19 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 20 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 21 |
Correct |
7 ms |
2808 KB |
Output is correct |
| 22 |
Correct |
115 ms |
2816 KB |
Output is correct |
| 23 |
Correct |
66 ms |
2808 KB |
Output is correct |
| 24 |
Correct |
72 ms |
2824 KB |
Output is correct |
| 25 |
Correct |
72 ms |
2936 KB |
Output is correct |
| 26 |
Correct |
64 ms |
2824 KB |
Output is correct |
| 27 |
Correct |
38 ms |
2824 KB |
Output is correct |
| 28 |
Correct |
48 ms |
2824 KB |
Output is correct |
| 29 |
Correct |
81 ms |
2908 KB |
Output is correct |
| 30 |
Correct |
71 ms |
2808 KB |
Output is correct |
