# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
528147 | 2022-02-19T12:43:51 Z | buidangnguyen05 | Skyscraper (JOI16_skyscraper) | C++14 | 104 ms | 29412 KB |
/* input */ #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 110, mod = 1e9 + 7; int a[N], f[N][N][10 * N][3]; void add(int &x, int y) { x += y; if (x >= mod) x -= mod; } signed main() { cin.tie(0)->sync_with_stdio(0); if (fopen("task.inp", "r")) { freopen("task.inp", "r", stdin); freopen("task.out", "w", stdout); } int n, mx; cin >> n >> mx; for (int i = 1; i <= n; ++i) cin >> a[i]; if (n == 1) { cout << "1\n"; exit(0); } sort (a + 1, a + n + 1); a[n + 1] = 1e5; f[0][0][0][0] = 1; for (int i = 1; i <= n; ++i) for (int j = 1; j <= i; ++j) { for (int k = 1; k <= mx; ++k) for (int m = 0; m < 3; ++m) { int diff = (2 * j - m) * (a[i + 1] - a[i]); if (diff > k || i + j + 1 - m > n) continue; add(f[i][j][k][m], f[i - 1][j - 1][k - diff][m]); if (m) add(f[i][j][k][m], 1LL * (3 - m) * f[i - 1][j - 1][k - diff][m - 1] % mod); add(f[i][j][k][m], 1LL * (2 * j - m) * f[i - 1][j][k - diff][m] % mod); if (m == 1) add(f[i][j][k][m], 2LL * j * f[i - 1][j][k - diff][m - 1] % mod); else if (m == 2) { if (i == n) add(f[i][j][k][m], f[i - 1][j][k - diff][m - 1]); else add(f[i][j][k][m], 1LL * (j - 1) * f[i - 1][j][k - diff][m - 1] % mod); } if (m == 1) add(f[i][j][k][m], 1LL * j * j * f[i - 1][j + 1][k - diff][m] % mod); else if (!m) add(f[i][j][k][m], 1LL * j * (j + 1) * f[i - 1][j + 1][k - diff][m] % mod); else { if (i == n) add(f[i][j][k][m], f[i - 1][j + 1][k - diff][m]); else add(f[i][j][k][m], 1LL * j * (j - 1) * f[i - 1][j + 1][k - diff][m] % mod); } } } int res = 0; for (int i = 0; i <= mx; ++i) add(res, f[n][1][i][2]); cout << res << "\n"; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 0 ms | 332 KB | Output is correct |
4 | Correct | 0 ms | 332 KB | Output is correct |
5 | Correct | 1 ms | 588 KB | Output is correct |
6 | Correct | 1 ms | 460 KB | Output is correct |
7 | Correct | 0 ms | 332 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 ms | 460 KB | Output is correct |
10 | Correct | 1 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 460 KB | Output is correct |
2 | Correct | 1 ms | 588 KB | Output is correct |
3 | Correct | 1 ms | 588 KB | Output is correct |
4 | Correct | 1 ms | 588 KB | Output is correct |
5 | Correct | 1 ms | 460 KB | Output is correct |
6 | Correct | 1 ms | 588 KB | Output is correct |
7 | Correct | 0 ms | 460 KB | Output is correct |
8 | Correct | 1 ms | 588 KB | Output is correct |
9 | Correct | 1 ms | 588 KB | Output is correct |
10 | Correct | 1 ms | 588 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 0 ms | 332 KB | Output is correct |
4 | Correct | 0 ms | 332 KB | Output is correct |
5 | Correct | 1 ms | 588 KB | Output is correct |
6 | Correct | 1 ms | 460 KB | Output is correct |
7 | Correct | 0 ms | 332 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 ms | 460 KB | Output is correct |
10 | Correct | 1 ms | 332 KB | Output is correct |
11 | Correct | 1 ms | 460 KB | Output is correct |
12 | Correct | 1 ms | 588 KB | Output is correct |
13 | Correct | 1 ms | 588 KB | Output is correct |
14 | Correct | 1 ms | 588 KB | Output is correct |
15 | Correct | 1 ms | 460 KB | Output is correct |
16 | Correct | 1 ms | 588 KB | Output is correct |
17 | Correct | 0 ms | 460 KB | Output is correct |
18 | Correct | 1 ms | 588 KB | Output is correct |
19 | Correct | 1 ms | 588 KB | Output is correct |
20 | Correct | 1 ms | 588 KB | Output is correct |
21 | Correct | 2 ms | 2124 KB | Output is correct |
22 | Correct | 94 ms | 20616 KB | Output is correct |
23 | Correct | 104 ms | 27528 KB | Output is correct |
24 | Correct | 90 ms | 28520 KB | Output is correct |
25 | Correct | 99 ms | 29104 KB | Output is correct |
26 | Correct | 86 ms | 27476 KB | Output is correct |
27 | Correct | 37 ms | 17056 KB | Output is correct |
28 | Correct | 48 ms | 18668 KB | Output is correct |
29 | Correct | 85 ms | 25924 KB | Output is correct |
30 | Correct | 101 ms | 29412 KB | Output is correct |