QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#639666 | #6606. The Boomsday Project | rerebornzhou | WA | 683ms | 8284kb | C++20 | 1.4kb | 2024-10-13 21:16:14 | 2024-10-13 21:16:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
#define ull unsigned long long
#define fi first
#define se second
#define pi pair<int,int>
const int N=1e6+10;
const int INF=1e18;
struct node{
int p,q;
};
unordered_map<int,int> mp;
void solve(){
int n,m,r;
cin>>n>>m>>r;
mp.clear();
vector<int> d(n+1),k(n+1),c(n+1);
for(int i=1;i<=n;i++){
cin>>d[i]>>k[i]>>c[i];
}
vector<node> a(m+1);
int sq=0;
for(int i=1;i<=m;i++){
cin>>a[i].p>>a[i].q;
sq+=a[i].q;
}
sort(a.begin(),a.end(),[&](node a,node b){ return a.p<b.p;});
vector<int> day(sq+1);
int last=0;
for(int i=1;i<=m;i++){
for(int j=last+1;j<=last+a[i].q;j++){
day[j]=a[i].p;
}
last=last+a[i].q;
mp[a[i].p]=last;
}
vector<int> f(sq+1,INF);
f[0]=0;
// for(int i=1;i<=sq;i++){
// cout<<day[i]<<" \n"[i==sq];
// }
for(int i=1;i<=sq;i++){
f[i]=f[i-1]+r;
for(int j=1;j<=n;j++){
f[i]=min({f[i],f[max(i-k[j],mp[day[i]-d[j]])]+c[j]});
// cout<<i<<" "<<day[i]<<" "<<d[j]<<" "<<mp[day[i]-d[j]]<<" "<<i-k[j]<<"\n";
}
}
// cout<<sq<<'\n';
cout<<f[sq]<<"\n";
}
signed main(){
int _=1;
// cin>>_;
while(_--){
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3848kb
input:
2 1 10 1 3 12 1 2 9 1 10
output:
42
result:
ok 1 number(s): "42"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
2 4 10 1 3 12 1 2 9 1 3 2 3 3 3 4 1
output:
45
result:
ok 1 number(s): "45"
Test #3:
score: 0
Accepted
time: 649ms
memory: 7528kb
input:
500 100 1000 95 20 20892 73 627 55354 52 747 1404314 19 676 597007 65 814 1569851 91 397 691575 81 4 4575 97 382 624404 21 197 201850 67 799 643576 27 895 1510533 3 800 552439 49 954 1149851 70 892 676406 82 882 1348956 1 318 324094 43 238 439111 94 397 471003 16 119 130686 1 637 77731 79 292 35234 ...
output:
450790
result:
ok 1 number(s): "450790"
Test #4:
score: 0
Accepted
time: 656ms
memory: 7996kb
input:
500 100 1000 8 910 1405086 65 931 697221 73 534 1051699 74 13 7497 64 631 991592 79 481 511568 92 892 477132 91 588 842013 21 389 750794 19 955 1333270 85 889 1334457 46 295 505372 83 486 449366 67 67 119659 82 446 408487 25 736 319997 31 889 23280 1 41 74813 93 928 1189573 88 468 455471 7 10 18865 ...
output:
3276270
result:
ok 1 number(s): "3276270"
Test #5:
score: 0
Accepted
time: 605ms
memory: 7332kb
input:
500 100 1000 35 122 153490 71 121 27207 73 967 409546 88 325 182835 37 602 533155 61 546 114146 70 359 251186 64 429 591088 63 445 428802 81 819 408704 49 364 244867 64 937 1422956 98 505 713891 1 454 61697 91 673 116038 89 463 123737 67 724 1061372 31 1 1838 73 127 173419 72 122 8068 55 928 65539 3...
output:
762564
result:
ok 1 number(s): "762564"
Test #6:
score: 0
Accepted
time: 661ms
memory: 7900kb
input:
500 100 1000 77 590 825100 67 901 1633566 29 703 886708 86 223 168970 6 676 1162365 46 669 1308904 73 96 125961 37 529 774376 79 741 516927 95 835 602321 25 208 384673 16 20 12510 41 226 164928 68 836 1412302 52 689 418717 40 481 789905 10 838 220638 35 846 885451 54 736 1470524 13 490 224433 12 354...
output:
300840
result:
ok 1 number(s): "300840"
Test #7:
score: 0
Accepted
time: 604ms
memory: 7408kb
input:
500 100 1000 39 154 45298 34 357 85100 46 557 748764 24 896 665708 97 28 1885 42 668 1223574 53 614 669616 28 648 1145794 28 649 1208449 93 689 1227367 56 772 163614 54 468 462959 28 400 721934 25 391 208246 55 388 473486 67 106 55488 63 10 18506 6 113 191992 43 100 165666 29 952 1200973 79 519 5596...
output:
1147818
result:
ok 1 number(s): "1147818"
Test #8:
score: 0
Accepted
time: 627ms
memory: 7540kb
input:
500 100 1000 25 155 54027 94 392 88410 71 600 1051186 31 391 104487 28 851 1539952 37 30 20168 26 722 164500 79 802 967771 68 481 152325 53 46 19203 91 445 398966 98 418 250634 96 387 128328 3 439 679797 13 201 81420 7 10 2504 75 139 213047 19 289 499368 1 100 44418 67 834 737897 87 235 57104 76 943...
output:
42900
result:
ok 1 number(s): "42900"
Test #9:
score: 0
Accepted
time: 550ms
memory: 7056kb
input:
500 100 1000 51 42 16628 43 190 172609 19 71 111541 5 307 90084 24 370 464785 40 728 4358 70 289 140870 12 834 1379849 1 832 380970 57 788 14539 99 217 116555 22 293 75003 64 508 504262 76 757 745132 82 508 111516 48 447 728589 94 91 128698 34 689 724690 55 206 140536 19 6 11110 54 148 284655 82 577...
output:
441300
result:
ok 1 number(s): "441300"
Test #10:
score: 0
Accepted
time: 620ms
memory: 7524kb
input:
500 100 1000 34 971 1557997 38 468 536953 16 133 88701 46 139 79800 35 5 2908 43 991 771999 55 595 439720 10 1 1409 20 235 373255 72 178 218511 67 164 252433 70 155 22009 46 838 1434022 29 13 16155 43 694 721903 1 142 134637 10 206 232264 79 235 138874 91 964 1840417 46 379 36314 91 541 105296 82 74...
output:
3846908
result:
ok 1 number(s): "3846908"
Test #11:
score: 0
Accepted
time: 663ms
memory: 7792kb
input:
500 100 1000 78 680 93658 91 681 935976 27 885 1219969 74 426 233941 88 143 257524 55 743 1279359 4 841 807430 52 61 58591 37 515 992872 67 440 525617 37 119 4821 96 164 47048 53 98 41919 46 451 804734 71 440 377656 45 988 1339930 79 983 1954579 14 16 8209 45 496 165715 46 391 163844 64 334 585656 3...
output:
147840
result:
ok 1 number(s): "147840"
Test #12:
score: 0
Accepted
time: 683ms
memory: 7796kb
input:
500 100 1000 17 337 520830 13 320 435598 34 344 332171 1 779 442379 32 280 282 55 615 1050064 55 55 101465 49 434 119384 33 728 285107 37 378 345293 4 575 419615 18 929 254491 10 82 30957 57 704 240496 55 39 9470 63 193 273163 27 208 298983 45 721 493246 20 427 255468 76 733 1062484 91 514 670590 1 ...
output:
300330
result:
ok 1 number(s): "300330"
Test #13:
score: 0
Accepted
time: 652ms
memory: 7888kb
input:
500 100 500000 88 337 305883611 41 175 37057752 49 55 39547475 40 419 77409822 53 926 95898196 88 305 282306241 64 472 150142072 67 722 627918523 64 734 45315633 97 396 275395403 67 341 286394272 1 808 40798374 54 763 4529294 30 206 157558711 72 937 593507461 39 967 634291057 73 279 193814503 22 166...
output:
7958679
result:
ok 1 number(s): "7958679"
Test #14:
score: 0
Accepted
time: 629ms
memory: 7660kb
input:
500 100 500000 48 291 77324210 55 803 201189051 80 613 86857684 37 295 209966905 19 973 81478590 86 601 110983393 66 964 291658381 60 112 77757355 61 846 15731458 86 235 168473182 89 136 14994111 92 540 92431585 59 215 134606352 89 575 9269688 71 22 15341815 38 50 17724764 37 792 70648577 37 619 228...
output:
79212560
result:
ok 1 number(s): "79212560"
Test #15:
score: 0
Accepted
time: 652ms
memory: 7716kb
input:
500 100 500000 64 664 92524273 95 898 890754323 1 352 158420593 49 259 36712015 53 685 114613304 72 430 68130085 59 673 410775795 52 953 252202681 91 19 15952819 34 1 682089 1 683 485683885 89 122 22249286 3 331 280433737 28 805 54297100 75 206 198492355 35 353 152254081 55 515 426325231 18 600 2379...
output:
114964628
result:
ok 1 number(s): "114964628"
Test #16:
score: 0
Accepted
time: 614ms
memory: 7560kb
input:
500 100 500000 5 706 80771411 89 292 46009981 82 685 198826346 34 76 18282733 34 912 53442973 37 459 58657141 86 618 162695850 26 291 256158377 97 676 342326785 25 200 9186714 12 301 21336363 73 966 257245547 58 913 68981482 37 325 17384036 97 691 68915352 43 263 14894675 97 744 220748347 59 265 117...
output:
132025996
result:
ok 1 number(s): "132025996"
Test #17:
score: 0
Accepted
time: 662ms
memory: 7664kb
input:
500 100 500000 72 499 85157330 65 668 402065169 76 631 136078671 34 259 52726521 19 21 1526977 93 25 13513520 49 83 14052025 16 114 54732239 12 460 263225401 89 253 39225643 74 229 132679456 99 760 340672861 1 722 225419801 82 35 6430447 10 23 18130531 62 279 161129003 91 226 203120137 17 783 263011...
output:
30194785
result:
ok 1 number(s): "30194785"
Test #18:
score: 0
Accepted
time: 624ms
memory: 7632kb
input:
500 100 500000 14 865 3462216 81 815 302995417 73 535 473631124 67 786 468787159 91 224 109097456 85 139 48202412 43 782 33553936 58 933 39518707 30 502 257510839 1 809 78008815 82 377 267465561 45 413 28023932 6 176 109303043 24 178 121890167 43 964 672867649 28 530 52807595 88 656 72050224 19 184 ...
output:
139452477
result:
ok 1 number(s): "139452477"
Test #19:
score: 0
Accepted
time: 660ms
memory: 7956kb
input:
500 100 500000 91 157 90000268 85 202 65400524 19 87 65854317 2 784 199206406 31 385 71919388 44 454 228454078 62 27 26221013 40 772 136004980 98 547 451215803 63 693 56256549 25 349 29986924 19 17 12496438 49 859 25962715 82 802 41624289 19 381 153612451 17 109 70823152 45 671 163997107 49 201 1408...
output:
9589965
result:
ok 1 number(s): "9589965"
Test #20:
score: 0
Accepted
time: 613ms
memory: 7672kb
input:
500 100 500000 98 328 294265795 46 730 467761075 25 10 8963806 46 10 4897491 23 470 240258529 74 679 312776671 82 963 12205175 67 418 59720525 1 379 51929221 46 261 152905862 62 767 517344334 27 397 208108235 15 912 194493590 59 135 127130395 55 877 13946562 15 524 403763035 44 301 22555681 73 616 2...
output:
18704981
result:
ok 1 number(s): "18704981"
Test #21:
score: 0
Accepted
time: 645ms
memory: 7884kb
input:
500 100 500000 70 28 12290551 98 374 365080617 39 808 120996209 10 478 14058145 55 586 207845662 24 77 56748997 18 797 311534209 87 662 55884169 88 892 380907793 7 757 137316691 43 289 26295795 34 641 56952169 72 400 6307945 43 925 520243276 23 604 390825282 1 985 10709969 24 832 56014037 5 595 2152...
output:
114734046
result:
ok 1 number(s): "114734046"
Test #22:
score: 0
Accepted
time: 618ms
memory: 7552kb
input:
500 100 500000 33 787 18617873 69 96 3342361 45 772 99254378 97 37 33415789 68 401 342282709 35 535 107981309 96 752 15176305 46 175 46186691 13 678 62106220 14 574 428383473 28 579 12765311 27 782 411868535 78 555 332689237 7 567 11369695 40 151 78401699 15 61 40150307 38 621 31517175 73 385 850029...
output:
39127150
result:
ok 1 number(s): "39127150"
Test #23:
score: 0
Accepted
time: 620ms
memory: 7616kb
input:
500 2 1000 1 20 20892 1 627 55354 1 747 1404314 1 676 597007 1 814 1569851 1 397 691575 1 4 4575 1 382 624404 1 197 201850 1 799 643576 1 895 1510533 1 800 552439 1 954 1149851 1 892 676406 1 882 1348956 1 318 324094 1 238 439111 1 397 471003 1 119 130686 1 637 77731 1 292 35234 1 243 348565 1 332 2...
output:
453596
result:
ok 1 number(s): "453596"
Test #24:
score: 0
Accepted
time: 482ms
memory: 6964kb
input:
500 2 1000 1 525 987507 1 92 28315 1 655 631455 1 42 27847 1 3 2031 1 886 1541395 1 616 903748 1 140 259414 1 870 359120 1 502 419577 1 700 133293 1 899 440910 1 568 920335 1 108 166882 1 865 557725 1 829 1076839 1 417 141389 1 190 365986 1 652 67148 1 437 135833 1 720 634181 1 437 464374 1 253 1253...
output:
558545
result:
ok 1 number(s): "558545"
Test #25:
score: 0
Accepted
time: 580ms
memory: 7664kb
input:
500 2 1000 1 230 313202 1 841 786856 1 562 1106407 1 118 221149 1 607 135212 1 142 275635 1 361 177717 1 967 325151 1 847 116256 1 7 3899 1 937 1571908 1 424 29177 1 452 507919 1 781 1255985 1 664 420150 1 134 180586 1 738 961612 1 246 471837 1 781 1211881 1 904 1147376 1 161 6584 1 832 1098686 1 56...
output:
2524566
result:
ok 1 number(s): "2524566"
Test #26:
score: 0
Accepted
time: 638ms
memory: 7932kb
input:
500 2 1000 1 256 471450 1 520 914190 1 217 129973 1 578 288473 1 66 57103 1 479 579870 1 135 30821 1 328 400054 1 930 1625351 1 834 912799 1 712 698720 1 200 289942 1 154 4613 1 193 282323 1 635 686599 1 817 1143189 1 482 659647 1 2 3613 1 798 155016 1 450 542961 1 256 480685 1 298 264533 1 648 1287...
output:
1161132
result:
ok 1 number(s): "1161132"
Test #27:
score: 0
Accepted
time: 527ms
memory: 7072kb
input:
500 2 1000 1 778 935019 1 778 1279930 1 489 385890 1 166 20905 1 544 296080 1 537 104811 1 205 136906 1 126 25221 1 97 181203 1 358 235607 1 230 420859 1 452 103675 1 614 1206685 1 487 336880 1 81 105199 1 203 239566 1 751 1501191 1 16 22750 1 478 731853 1 116 98816 1 501 822721 1 402 129998 1 171 2...
output:
2048000
result:
ok 1 number(s): "2048000"
Test #28:
score: 0
Accepted
time: 549ms
memory: 7424kb
input:
500 2 1000 1 43 5541 1 145 178512 1 568 797703 1 676 1156399 1 48 20556 1 666 1084477 1 613 874562 1 115 229222 1 838 12776 1 37 4240 1 433 232770 1 149 208649 1 859 1502448 1 823 607270 1 557 209887 1 30 8917 1 946 1515935 1 181 108501 1 610 14281 1 649 71934 1 570 574552 1 679 735423 1 250 421609 ...
output:
1532601
result:
ok 1 number(s): "1532601"
Test #29:
score: 0
Accepted
time: 610ms
memory: 7524kb
input:
500 2 1000 1 76 132414 1 805 983406 1 539 476698 1 20 14980 1 455 426628 1 865 526788 1 719 1371458 1 235 74353 1 563 650067 1 928 334812 1 62 20656 1 403 212518 1 790 232018 1 227 10492 1 88 130360 1 811 1402221 1 656 1234662 1 372 413162 1 217 416241 1 463 248133 1 601 826995 1 196 367471 1 208 18...
output:
435918
result:
ok 1 number(s): "435918"
Test #30:
score: 0
Accepted
time: 529ms
memory: 7040kb
input:
500 2 1000 1 685 462336 1 847 1525819 1 835 86362 1 978 1764196 1 856 446571 1 34 12986 1 596 194319 1 229 38276 1 343 492923 1 470 526324 1 112 180187 1 239 172474 1 213 417967 1 778 929237 1 108 55355 1 861 1682258 1 190 131428 1 312 72644 1 689 112893 1 811 847337 1 179 51582 1 886 51309 1 571 94...
output:
3685
result:
ok 1 number(s): "3685"
Test #31:
score: 0
Accepted
time: 625ms
memory: 7932kb
input:
500 2 1000 1 312 307329 1 508 164968 1 781 760215 1 811 1028641 1 487 300192 1 610 178976 1 376 179339 1 544 500087 1 298 30710 1 105 183890 1 732 614311 1 943 195290 1 756 222465 1 149 99864 1 100 179632 1 662 1239639 1 808 777874 1 622 256185 1 177 189343 1 17 19480 1 772 1092661 1 552 263508 1 95...
output:
15540
result:
ok 1 number(s): "15540"
Test #32:
score: 0
Accepted
time: 530ms
memory: 6816kb
input:
500 2 1000 1 46 19203 1 445 398966 1 418 250634 1 387 128328 1 439 679797 1 201 81420 1 10 2504 1 139 213047 1 289 499368 1 100 44418 1 834 737897 1 235 57104 1 943 750995 1 633 602973 1 566 1130728 1 562 119948 1 508 315452 1 103 20053 1 538 560044 1 325 189210 1 552 911298 1 833 784630 1 808 39318...
output:
35805
result:
ok 1 number(s): "35805"
Test #33:
score: -100
Wrong Answer
time: 633ms
memory: 8284kb
input:
500 100 1000 67 290 476380 21 703 1028496 35 52 100444 88 523 617114 1 607 1046903 36 451 529682 23 658 612301 42 636 307280 67 313 316282 1 666 1154728 13 621 992262 10 880 493415 22 966 661359 65 42 74641 37 173 114865 12 951 1335991 19 384 579204 65 822 1047603 35 670 610295 73 949 1741869 77 425...
output:
104748
result:
wrong answer 1st numbers differ - expected: '105266', found: '104748'