QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #375827 | #5552. Skyscraper | qingyu | 100 ✓ | 24ms | 21840kb | C++23 | 1.6kb | 2024-04-03 16:17:15 | 2024-04-03 16:17:17 |
Judging History
answer
// Problem: P9197 [JOI Open 2016] 摩天大楼
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9197
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//And from now on, YOU are my GUIDING STAR.
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int p=1e9+7;
int f[103][103][3003][3],a[103],b[103];
signed main()
{
int n=read(),L=read(),ans=0;
if(n==1) puts("1"),exit(0);
for(int i=1; i<=n; ++i) a[i]=read();
sort(a+1,a+n+1),f[0][1][0][2]=1,L+=a[n]*2;
for(int i=1; i<=n; ++i) b[i]=(a[i]-a[i-1])*2;
for(int i=1; i<=n; ++i)
for(int j=1; j<=i; ++j)
for(int k=0; k+j*b[i]<=L; ++k)
for(int l=0; l<3; ++l) if(f[i-1][j][k][l])
{
//Minimum
f[i][j+1][k+j*b[i]][l]=
(f[i][j+1][k+j*b[i]][l]
+1ll*j*f[i-1][j][k][l])%p;
//Medium
f[i][j][k+j*b[i]][l]=
(f[i][j][k+j*b[i]][l]
+1ll*(j*2-l)*f[i-1][j][k][l])%p;
if(l&&k+j*b[i]+a[n]-a[i]<=L)
f[i][j][k+j*b[i]+a[n]-a[i]][l-1]=
(f[i][j][k+j*b[i]+a[n]-a[i]][l-1]
+1ll*l*f[i-1][j][k][l])%p;
//Maximum
if(j-l>0)
f[i][j-1][k+j*b[i]][l]=
(f[i][j-1][k+j*b[i]][l]
+1ll*(j-l)*f[i-1][j][k][l])%p;
if(l&&k+j*b[i]+a[n]-a[i]<=L)
f[i][j-1][k+j*b[i]+a[n]-a[i]][l-1]=
(f[i][j-1][k+j*b[i]+a[n]-a[i]][l-1]
+1ll*l*f[i-1][j][k][l])%p;
}
for(int i=0; i<=L; ++i) ans=(ans+f[n][0][i][0])%p;
printf("%d\n",ans);
return 0;
}
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 3488kb
input:
1 1 8
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
2 6 10 4
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
3 11 9 1 3
output:
4
result:
ok single line: '4'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3956kb
input:
6 94 45 79 24 10 41 66
output:
12
result:
ok single line: '12'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4164kb
input:
8 945 493 43 988 504 328 730 841 613
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4132kb
input:
8 846 304 170 710 158 561 934 100 279
output:
2
result:
ok single line: '2'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3992kb
input:
8 160 136 98 27 113 68 11 34 180
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 1ms
memory: 4024kb
input:
8 77 20 10 22 8 3 14 7 6
output:
39672
result:
ok single line: '39672'
Test #9:
score: 0
Accepted
time: 1ms
memory: 4188kb
input:
8 904 746 229 92 195 358 2 154 709
output:
30
result:
ok single line: '30'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3948kb
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: 1ms
memory: 4200kb
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: 1ms
memory: 4152kb
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: 1ms
memory: 4216kb
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: 1ms
memory: 4244kb
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: 1ms
memory: 4164kb
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: 1ms
memory: 6280kb
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: 0ms
memory: 4016kb
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: 1ms
memory: 4240kb
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: 1ms
memory: 4308kb
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: 1ms
memory: 4268kb
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: 0ms
memory: 5180kb
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: 20ms
memory: 21840kb
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: 15ms
memory: 18724kb
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: 17ms
memory: 18584kb
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: 24ms
memory: 20520kb
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: 24ms
memory: 18632kb
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: 8ms
memory: 13856kb
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: 3ms
memory: 15496kb
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: 12ms
memory: 19096kb
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: 24ms
memory: 20240kb
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