QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #559855 | #5552. Skyscraper | user10086 | 15 | 1ms | 4816kb | C++17 | 1.2kb | 2024-09-12 09:55:51 | 2024-09-12 09:55:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 110, M = 1e3 + 10, MOD = 1e9 + 7;
int n, L, dp[N][N][M][3], a[N];
void add(int& x, int y)
{
(x += y) %= MOD;
}
signed main()
{
cin >> n >> L;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n == 1)
{
cout << 1;
return 0;
}
sort(a + 1, a + 1 + n);
dp[0][0][0][0] = 1;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= i; j++)
for (int l = 0; l <= L; l++)
for (int k = 0; k <= 2; k++)
{
// printf("dp(%lld, %lld, %lld, %lld) = %lld\n", i, j, l, k, dp[i][j][l][k]);
int d = a[i + 1] - a[i];
int nxt = l + d * (2 * j - k);
if (nxt > L) continue;
add(dp[i + 1][j + 1][nxt][k], dp[i][j][l][k] * (j + 1 - k));
if (k < 2) add(dp[i + 1][j + 1][nxt][k + 1], dp[i][j][l][k] * (2 - k));
if (j > 0) add(dp[i + 1][j - 1][nxt][k], dp[i][j][l][k] * (j - 1));
add(dp[i + 1][j][nxt][k], dp[i][j][l][k] * (2 * j - k));
if (k < 2) add(dp[i + 1][j][nxt][k + 1], dp[i][j][l][k] * (2 - k));
}
int ans = 0;
for (int l = 0; l <= L; l++) (ans += dp[n][1][l][2]) %= MOD;
cout << ans;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 0ms
memory: 3584kb
input:
1 1 8
output:
1
result:
ok single line: '1'
Test #2:
score: 5
Accepted
time: 0ms
memory: 3656kb
input:
2 6 10 4
output:
2
result:
ok single line: '2'
Test #3:
score: 5
Accepted
time: 0ms
memory: 3596kb
input:
3 11 9 1 3
output:
4
result:
ok single line: '4'
Test #4:
score: 5
Accepted
time: 0ms
memory: 3800kb
input:
6 94 45 79 24 10 41 66
output:
12
result:
ok single line: '12'
Test #5:
score: 0
Wrong Answer
time: 1ms
memory: 4816kb
input:
8 945 493 43 988 504 328 730 841 613
output:
34
result:
wrong answer 1st lines differ - expected: '2', found: '34'
Subtask #2:
score: 15
Accepted
Test #11:
score: 15
Accepted
time: 1ms
memory: 4300kb
input:
12 63 8 2 6 3 11 9 1 12 4 5 10 7
output:
472261248
result:
ok single line: '472261248'
Test #12:
score: 15
Accepted
time: 1ms
memory: 4492kb
input:
14 96 17 36 98 27 13 68 11 34 80 50 22 73 94 37
output:
44
result:
ok single line: '44'
Test #13:
score: 15
Accepted
time: 1ms
memory: 4372kb
input:
14 45 6 9 12 15 18 2 14 5 11 17 4 3 7 10
output:
183056086
result:
ok single line: '183056086'
Test #14:
score: 15
Accepted
time: 1ms
memory: 4480kb
input:
14 97 25 2 54 78 9 29 34 99 82 36 14 66 15 64
output:
2
result:
ok single line: '2'
Test #15:
score: 15
Accepted
time: 0ms
memory: 4520kb
input:
14 98 26 70 16 95 30 2 18 96 6 5 52 99 89 24
output:
2
result:
ok single line: '2'
Test #16:
score: 15
Accepted
time: 0ms
memory: 4496kb
input:
14 92 33 3 17 38 39 45 2 48 22 29 9 28 5 10
output:
1235526
result:
ok single line: '1235526'
Test #17:
score: 15
Accepted
time: 1ms
memory: 4272kb
input:
14 29 12 6 16 9 23 20 3 1 8 25 29 26 19 24
output:
2
result:
ok single line: '2'
Test #18:
score: 15
Accepted
time: 0ms
memory: 4400kb
input:
14 43 17 11 7 8 5 2 10 16 12 9 15 3 14 18
output:
110733412
result:
ok single line: '110733412'
Test #19:
score: 15
Accepted
time: 1ms
memory: 4396kb
input:
14 72 7 13 19 16 20 15 4 10 1 6 14 11 5 8
output:
347124497
result:
ok single line: '347124497'
Test #20:
score: 15
Accepted
time: 1ms
memory: 4484kb
input:
14 83 18 73 40 48 86 97 24 21 45 69 36 16 26 35
output:
6
result:
ok single line: '6'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%