QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #390171 | #5552. Skyscraper | iee | 100 ✓ | 902ms | 406440kb | C++23 | 1.1kb | 2024-04-15 09:20:57 | 2024-04-15 09:20:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 105, M = 6666, P = 1e9 + 7;
int n, m, a[N], f[N][N][M][3];
void add(int &x, int y) {
x += y;
if (x >= P) x -= P;
}
int main() {
cin >> n >> m;
if (n == 1) {
cout << 1 << "\n";
return 0;
}
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1, greater<>());
f[0][0][0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
for (int k = 0; k < M; k++) {
for (int s = 0; s <= 2; s++) {
int v = f[i][j][k][s];
if (k + 2 * a[i + 1] < M) add(f[i + 1][j + 1][k + 2 * a[i + 1]][s], 1ll * v * (j + 1 - s) % P);
if (k + a[i + 1] < M && s < 2) add(f[i + 1][j + 1][k + a[i + 1]][s + 1], v * (2 - s) % P);
if (j && k >= a[i + 1] * 2) add(f[i + 1][j - 1][k - a[i + 1] * 2][s], 1ll * v * (j - 1) % P);
add(f[i + 1][j][k][s], 1ll * v * (2 * j - s) % P);
if (k >= a[i + 1] && s < 2) add(f[i + 1][j][k - a[i + 1]][s + 1], 1ll * v * (2 - s) % P);
}
}
}
}
int ans = 0;
for (int k = 0; k <= m; k++) {
add(ans, f[n][1][k][2]);
}
cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 1ms
memory: 3700kb
input:
1 1 8
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4052kb
input:
2 6 10 4
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 2ms
memory: 4292kb
input:
3 11 9 1 3
output:
4
result:
ok single line: '4'
Test #4:
score: 0
Accepted
time: 5ms
memory: 5760kb
input:
6 94 45 79 24 10 41 66
output:
12
result:
ok single line: '12'
Test #5:
score: 0
Accepted
time: 4ms
memory: 7080kb
input:
8 945 493 43 988 504 328 730 841 613
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 8ms
memory: 7160kb
input:
8 846 304 170 710 158 561 934 100 279
output:
2
result:
ok single line: '2'
Test #7:
score: 0
Accepted
time: 5ms
memory: 7056kb
input:
8 160 136 98 27 113 68 11 34 180
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 8ms
memory: 7048kb
input:
8 77 20 10 22 8 3 14 7 6
output:
39672
result:
ok single line: '39672'
Test #9:
score: 0
Accepted
time: 5ms
memory: 7160kb
input:
8 904 746 229 92 195 358 2 154 709
output:
30
result:
ok single line: '30'
Test #10:
score: 0
Accepted
time: 5ms
memory: 7172kb
input:
8 121 19 41 25 47 31 4 23 17
output:
24760
result:
ok single line: '24760'
Subtask #2:
score: 15
Accepted
Test #11:
score: 15
Accepted
time: 17ms
memory: 10716kb
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: 0
Accepted
time: 19ms
memory: 12984kb
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: 0
Accepted
time: 15ms
memory: 13060kb
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: 0
Accepted
time: 11ms
memory: 13056kb
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: 0
Accepted
time: 19ms
memory: 13004kb
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: 0
Accepted
time: 19ms
memory: 13060kb
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: 0
Accepted
time: 15ms
memory: 12988kb
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: 0
Accepted
time: 19ms
memory: 12992kb
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: 0
Accepted
time: 19ms
memory: 13048kb
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: 0
Accepted
time: 11ms
memory: 12992kb
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: 80
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #21:
score: 80
Accepted
time: 144ms
memory: 70944kb
input:
40 39 14 4 18 1 31 32 21 19 37 15 40 33 30 23 10 12 24 11 39 27 20 22 17 5 25 2 6 35 26 13 29 38 9 36 34 28 8 3 7 16
output:
2
result:
ok single line: '2'
Test #22:
score: 0
Accepted
time: 532ms
memory: 250720kb
input:
78 822 11 17 6 74 82 21 92 70 66 28 37 29 26 85 68 50 77 47 67 59 12 45 19 35 90 15 30 41 55 97 36 84 49 53 65 38 76 46 16 93 48 100 94 80 2 34 1 71 18 39 44 22 20 89 60 88 13 62 32 4 99 40 5 8 25 7 51 33 42 78 23 63 9 58 56 31 95 57
output:
519066706
result:
ok single line: '519066706'
Test #23:
score: 0
Accepted
time: 826ms
memory: 406000kb
input:
100 982 571 304 440 915 800 767 836 922 44 753 87 720 151 411 624 670 606 944 312 432 993 817 700 972 640 371 837 892 858 834 329 178 684 177 490 92 435 712 905 27 791 523 365 891 885 814 442 128 180 785 538 871 562 582 166 803 733 333 855 760 848 378 463 11 820 942 721 300 113 957 391 153 49 15 45 ...
output:
2
result:
ok single line: '2'
Test #24:
score: 0
Accepted
time: 901ms
memory: 406328kb
input:
100 742 251 236 416 365 495 464 259 153 93 317 215 421 61 451 369 242 348 197 288 2 235 129 72 449 376 254 372 330 294 220 472 321 265 80 131 411 81 114 343 139 383 45 329 394 76 481 1 97 448 371 88 44 234 353 262 325 401 381 279 358 424 499 15 346 163 10 111 350 219 291 56 244 386 35 276 322 152 22...
output:
44225906
result:
ok single line: '44225906'
Test #25:
score: 0
Accepted
time: 783ms
memory: 406124kb
input:
100 994 314 762 11 841 979 1 395 508 657 552 787 432 545 740 777 585 253 109 515 455 20 29 672 371 664 948 25 544 855 9 982 553 289 164 360 380 357 462 488 354 900 789 245 881 467 284 275 237 910 568 835 940 685 652 550 267 468 111 590 328 774 582 296 937 875 436 232 973 799 71 588 298 90 647 91 112...
output:
20
result:
ok single line: '20'
Test #26:
score: 0
Accepted
time: 831ms
memory: 406192kb
input:
100 845 122 357 219 392 501 197 521 305 800 730 745 776 71 17 600 681 289 253 129 1 463 41 750 786 184 516 260 479 360 162 383 49 55 641 182 371 429 252 345 270 796 470 311 173 324 126 220 451 632 44 647 271 595 211 793 665 725 320 21 763 462 526 235 350 491 523 661 94 729 323 382 767 69 624 723 240...
output:
964691650
result:
ok single line: '964691650'
Test #27:
score: 0
Accepted
time: 890ms
memory: 406288kb
input:
100 244 54 13 26 41 58 34 96 40 52 59 95 61 39 30 76 99 93 63 77 37 47 74 65 85 20 43 29 60 46 17 28 73 49 1 71 44 64 84 2 10 22 87 14 70 32 57 55 15 16 38 67 98 78 92 75 25 51 100 45 80 35 8 11 97 62 21 69 88 27 42 5 18 72 36 89 79 24 9 7 56 19 33 66 94 48 31 68 83 6 53 86 4 3 90 23 12 50 82 81 91
output:
806509145
result:
ok single line: '806509145'
Test #28:
score: 0
Accepted
time: 895ms
memory: 406440kb
input:
100 300 20 11 12 16 79 43 46 71 63 9 84 100 10 14 51 52 66 3 18 54 17 85 70 4 30 58 83 65 53 55 27 28 56 60 87 23 50 80 99 91 44 86 88 32 77 62 64 15 33 92 72 34 31 81 5 82 59 41 37 39 13 96 22 78 42 21 98 38 6 8 40 25 47 94 97 24 45 36 2 49 95 76 90 68 26 74 67 19 75 35 93 48 7 57 69 61 73 29 1 89
output:
426165212
result:
ok single line: '426165212'
Test #29:
score: 0
Accepted
time: 902ms
memory: 406412kb
input:
100 572 133 160 57 146 103 124 90 20 95 87 108 193 101 147 2 166 145 157 75 118 176 96 67 65 92 192 141 60 98 110 164 23 86 100 120 121 149 54 177 77 34 198 194 104 9 175 167 31 182 187 126 70 26 159 186 200 22 115 61 73 156 163 49 53 71 32 1 64 148 171 183 180 197 30 102 131 21 152 46 55 158 94 16 ...
output:
608022944
result:
ok single line: '608022944'
Test #30:
score: 0
Accepted
time: 800ms
memory: 406092kb
input:
100 999 195 528 657 37 217 348 814 585 258 861 558 601 237 514 534 476 911 163 267 807 109 508 174 538 897 56 225 467 409 834 562 572 577 115 915 290 736 860 639 695 461 928 344 843 456 122 712 581 613 810 691 484 546 439 435 939 765 482 841 551 119 176 599 275 688 589 821 783 806 735 221 47 904 621...
output:
218730
result:
ok single line: '218730'
Extra Test:
score: 0
Extra Test Passed