///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int mod = 1e9 + 7;
int a[101], n, L;
int dp[101][101][3][1001];
void add(int &a, int b) { if((a += b) >= mod) a -= mod; }
#define mul(a, b) ((ll)(a) * (b) % mod)
int f(int i, int c, int e, int cost) {
cost += (a[i] - a[i - 1]) * (2 * c + e);
if(c < 0 || e > 2 || cost > L) return 0;
if(i == n) return c == 0 && e;
int &ret = dp[i][c][e][cost];
if(~ret) return ret;
ret = 0;
add(ret, mul(c + 1, f(i + 1, c + 1, e, cost)));
add(ret, mul(c + e - 1, f(i + 1, c - 1, e, cost)));
add(ret, mul(2 * c + e, f(i + 1, c, e, cost)));
add(ret, mul(2 - e, f(i + 1, c, e + 1, cost)));
add(ret, mul(2 - e, f(i + 1, c - 1, e + 1, cost)));
return ret;
}
int main() {
scanf("%d %d", &n, &L);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
sort(a + 1, a + n + 1);
memset(dp, -1, sizeof dp);
printf("%d\n", n == 1 ? 1 : f(1, 0, 0, 0));
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:34: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:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
120184 KB |
Output is correct |
| 2 |
Correct |
95 ms |
120336 KB |
Output is correct |
| 3 |
Correct |
81 ms |
120336 KB |
Output is correct |
| 4 |
Correct |
82 ms |
120448 KB |
Output is correct |
| 5 |
Correct |
82 ms |
120448 KB |
Output is correct |
| 6 |
Correct |
82 ms |
120448 KB |
Output is correct |
| 7 |
Correct |
84 ms |
120448 KB |
Output is correct |
| 8 |
Correct |
85 ms |
120448 KB |
Output is correct |
| 9 |
Correct |
94 ms |
120448 KB |
Output is correct |
| 10 |
Correct |
92 ms |
120448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
120448 KB |
Output is correct |
| 2 |
Correct |
93 ms |
120448 KB |
Output is correct |
| 3 |
Correct |
97 ms |
120484 KB |
Output is correct |
| 4 |
Correct |
93 ms |
120484 KB |
Output is correct |
| 5 |
Correct |
95 ms |
120484 KB |
Output is correct |
| 6 |
Correct |
83 ms |
120532 KB |
Output is correct |
| 7 |
Correct |
84 ms |
120532 KB |
Output is correct |
| 8 |
Correct |
86 ms |
120532 KB |
Output is correct |
| 9 |
Correct |
96 ms |
120532 KB |
Output is correct |
| 10 |
Correct |
93 ms |
120604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
120184 KB |
Output is correct |
| 2 |
Correct |
95 ms |
120336 KB |
Output is correct |
| 3 |
Correct |
81 ms |
120336 KB |
Output is correct |
| 4 |
Correct |
82 ms |
120448 KB |
Output is correct |
| 5 |
Correct |
82 ms |
120448 KB |
Output is correct |
| 6 |
Correct |
82 ms |
120448 KB |
Output is correct |
| 7 |
Correct |
84 ms |
120448 KB |
Output is correct |
| 8 |
Correct |
85 ms |
120448 KB |
Output is correct |
| 9 |
Correct |
94 ms |
120448 KB |
Output is correct |
| 10 |
Correct |
92 ms |
120448 KB |
Output is correct |
| 11 |
Correct |
93 ms |
120448 KB |
Output is correct |
| 12 |
Correct |
93 ms |
120448 KB |
Output is correct |
| 13 |
Correct |
97 ms |
120484 KB |
Output is correct |
| 14 |
Correct |
93 ms |
120484 KB |
Output is correct |
| 15 |
Correct |
95 ms |
120484 KB |
Output is correct |
| 16 |
Correct |
83 ms |
120532 KB |
Output is correct |
| 17 |
Correct |
84 ms |
120532 KB |
Output is correct |
| 18 |
Correct |
86 ms |
120532 KB |
Output is correct |
| 19 |
Correct |
96 ms |
120532 KB |
Output is correct |
| 20 |
Correct |
93 ms |
120604 KB |
Output is correct |
| 21 |
Correct |
96 ms |
120604 KB |
Output is correct |
| 22 |
Correct |
208 ms |
120604 KB |
Output is correct |
| 23 |
Correct |
177 ms |
120604 KB |
Output is correct |
| 24 |
Correct |
158 ms |
120604 KB |
Output is correct |
| 25 |
Correct |
161 ms |
120604 KB |
Output is correct |
| 26 |
Correct |
147 ms |
120604 KB |
Output is correct |
| 27 |
Correct |
108 ms |
120604 KB |
Output is correct |
| 28 |
Correct |
130 ms |
120604 KB |
Output is correct |
| 29 |
Correct |
183 ms |
120604 KB |
Output is correct |
| 30 |
Correct |
185 ms |
120604 KB |
Output is correct |
