QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#639666#6606. The Boomsday ProjectrerebornzhouWA 683ms8284kbC++201.4kb2024-10-13 21:16:142024-10-13 21:16:18

Judging History

你现在查看的是最新测评结果

  • [2024-10-13 21:16:18]
  • 评测
  • 测评结果:WA
  • 用时:683ms
  • 内存:8284kb
  • [2024-10-13 21:16:14]
  • 提交

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();
    }
}

Details

Tip: Click on the bar to expand more detailed information

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'