QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#141465#5690. 背包jrjyyAC ✓79ms3904kbC++20953b2023-08-17 14:21:102023-08-17 14:21:12

Judging History

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

  • [2023-08-17 14:21:12]
  • 评测
  • 测评结果:AC
  • 用时:79ms
  • 内存:3904kb
  • [2023-08-17 14:21:10]
  • 提交

answer

/* qoj_p5690.cpp */
#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 inf = 1e18;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, q; std::cin >> n >> q;
    std::vector<std::pair<int, int>> a(n);
    for (auto &[v, c] : a) std::cin >> v >> c;
    
    auto [m, w] = *std::max_element(a.begin(), a.end(), [](auto x, auto y) {
        return 1ll * x.second * y.first < 1ll * y.second * x.first;
    });
    std::vector<i64> f(m, -inf); f[0] = 0;
    for (auto [v, c] : a)
        for (int l = 0, lim = std::__gcd(m, v); l < lim; ++l)
            for (int i = l, x = 0; x < 2; x += i == l) {
                int j = (i + v) % m;
                f[j] = std::max(f[j], f[i] + c - 1ll * (i + v) / m * w);
                i = j;
            }
    
    while (q--) {
        i64 v; std::cin >> v;
        std::cout << std::max(f[v % m] + v / m * w, -1ll) << '\n';
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 3472kb

input:

50 100000
51305 277520
85830 111973
14837 979296
64100 235055
72474 557263
36773 232129
62774 398759
70740 834677
25120 999531
81191 28056
90133 884467
16462 693203
27057 616092
34713 932782
89420 663734
16437 298828
91123 516501
24430 267003
85485 535000
54839 145786
28114 187135
43791 474768
71273...

output:

811136115447000000
130312175752000000
831238227959000000
711780431949000000
567014385469000000
176643060888000000
532602712803000000
228620751332000000
434289249665000000
964750609099000000
271686175594000000
300113128686000000
853267533241000000
291269801555000000
450299770506000000
440721497066000...

result:

ok 100000 lines

Test #2:

score: 0
Accepted
time: 10ms
memory: 3488kb

input:

50 100000
97830 451823
37513 797833
61527 952574
98951 460952
9982 483106
39784 511945
98493 933482
90672 304557
73232 677587
81302 710167
50101 771645
1815 118770
32519 644183
79650 108103
13496 441661
46853 653992
17707 729081
40996 885010
30757 661427
36297 776622
63656 551419
58205 301706
50404 ...

output:

87402683733488322
48821086339507431
54200141913056370
27277013968053122
47783263639132800
39456586132249193
80866789029835593
63984560456175570
47041442747001970
31332172417359200
89341569089851001
43185914896957361
66381017294811522
71170240573169731
47735901033133922
27793564332294224
352626562721...

result:

ok 100000 lines

Test #3:

score: 0
Accepted
time: 18ms
memory: 3528kb

input:

50 100000
57263 689683
56297 264033
6254 774315
33923 212780
6212 547205
8250 668658
86884 679323
90655 998890
96634 362315
95661 541177
40681 728365
29251 318945
67206 418049
2303 471641
95083 531168
30415 507838
70429 863453
5068 974889
6841 89223
8041 645338
12274 135629
86594 169052
89426 798614...

output:

833769177988112
572090677551067
464406011426906
818311238036803
1003262593101894
1336412154649384
329762174052437
1424282613223876
283137801198865
513200208898777
1637543755241494
1500903213554974
759864122863173
1502802350468135
1231863031805930
446937204873378
830422276738924
896894387150280
19729...

result:

ok 100000 lines

Test #4:

score: 0
Accepted
time: 12ms
memory: 3536kb

input:

50 100000
18494 783117
27871 880374
9240 141155
88777 868504
31614 469656
54682 266336
73903 264144
69799 764433
37030 416907
24229 258867
31288 431580
38125 734733
38359 595082
21011 607598
76570 34351
18676 184727
34232 531927
45785 992426
85481 111898
33486 623833
29692 307948
16666 556170
50935 ...

output:

38623810694148
144946763634542
97231099112179
257850888125523
331524785992064
278600160971218
164361098471092
177155124854192
117032152448146
335939676920670
103210585498030
98309090219728
294994806569001
104987065617304
341219250633459
90013959444023
49269785767936
165310341961290
61142143266693
33...

result:

ok 100000 lines

Test #5:

score: 0
Accepted
time: 18ms
memory: 3576kb

input:

50 100000
78683 523491
13081 779961
75556 285324
19204 292954
73701 613598
13373 129108
67492 362483
24218 586632
14574 485692
21680 397143
59383 168482
94217 307620
84352 772543
22924 350057
36242 688838
96664 521058
27243 694241
39878 62956
42700 287856
45457 820528
18351 446340
69767 277466
83157...

output:

37519085868329
24507561853641
32108068555119
35735837863647
15271685639057
20478179070936
58611788877020
20559193767388
27659389424996
41178514258056
27665191814466
58034786533252
13005157817902
14903581256267
24490840413894
10692312977519
24287371542654
10027569734451
13833872243201
45946712205513
...

result:

ok 100000 lines

Test #6:

score: 0
Accepted
time: 73ms
memory: 3896kb

input:

50 100000
59960 29977
50680 25337
95900 47947
66600 33297
75060 37527
62620 31307
98040 49017
90280 45137
89420 44707
13580 6787
49780 24887
79020 39507
26920 13457
44360 22177
19980 9987
58600 29297
63120 31557
59420 29707
60080 30037
83420 41707
69500 34747
99480 49737
8400 4197
35840 17917
59840 ...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
294458059041
-1
-1
-1
94822437539
-1
-1
56956583622
-1
-1
-1
445752203772
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
178183763370
-1
107588338242
-1
226639511793
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
146566707165
-1
...

result:

ok 100000 lines

Test #7:

score: 0
Accepted
time: 77ms
memory: 3844kb

input:

50 100000
65412 327057
63744 318717
16672 83357
32276 161377
75002 375007
6474 32367
27520 137597
87848 439237
50404 252017
26986 134927
43592 217957
34920 174597
71640 358197
5436 27177
5886 29427
92138 460687
41700 208497
10528 52637
14048 70237
13902 69507
6912 34557
45396 226977
8594 42967
49000...

output:

1028953550537
-1
-1
922669181041
-1
-1
2636203394334
2263351470911
-1
4999011409557
-1
-1
3273633920658
-1
-1
4763039198381
-1
2146320253739
-1
4645553652747
2888839997901
1076872157219
1638093628668
-1
-1
-1
1612024665879
-1
1693113525378
4317338970865
968954545361
4830713234037
4451577884611
15724...

result:

ok 100000 lines

Test #8:

score: 0
Accepted
time: 40ms
memory: 3456kb

input:

50 100000
11359 24827
14238 30180
26261 53976
52183 115398
35531 79368
97907 215047
22935 47611
81831 177954
37064 80132
33428 72334
18280 36349
168 130
68424 150795
28551 62665
92840 204792
95822 211944
835 8
78731 175689
40943 87938
70956 158108
53418 118280
13906 26879
53232 114131
81318 178470
5...

output:

627651581043
1213117947389
1814092905809
1992894296581
1576264148602
844326514231
1285347013237
688129587313
435210130573
834708860757
989682276626
713734009327
1179772030597
2093982853638
435727388198
939689700366
501700821843
942677662634
1061983715796
1891827920610
2203269714604
482151020102
1343...

result:

ok 100000 lines

Test #9:

score: 0
Accepted
time: 14ms
memory: 3464kb

input:

50 100000
320 685991
109 233696
265 568279
194 416022
68 145600
63 134945
165 353573
234 501846
450 964996
83 177908
374 802050
95 203532
316 677416
461 988657
105 224908
306 655977
53 113447
254 544493
384 823315
296 634722
164 351477
350 750420
129 276419
201 430981
381 817006
252 540359
54 115771...

output:

1824354857975421
1934788375766682
816306338528427
1354460264465425
1697796964720623
1473440271326850
226608247562568
1446704193836885
1315062859629693
402739890164450
725274006557027
287638922051074
876907362831288
1882900552981617
2036001898850767
1829677361239410
2085080277969418
1647363748470834
...

result:

ok 100000 lines

Test #10:

score: 0
Accepted
time: 13ms
memory: 3640kb

input:

50 100000
870 73268
648 54583
8625 726553
89 7478
901 75894
48 4034
60 5050
994 83722
921 77566
72 6063
683 57520
7606 640703
296 24926
447 37654
676 56941
708 59637
500 42108
594 50024
11377 958375
761 64096
860 72431
995 83812
731 61559
737 62068
723 60888
976 82205
501 42198
955 80432
613 51622
3...

output:

63258428746671
49370766454513
27190670587009
62650507846917
57109485933041
71094001254341
70749044028491
55695923708771
59095224300783
32793645872904
69145446356054
63124249927418
35558042197195
59858921127656
24433979220653
46050712750360
58596180811643
83191148719340
16190562953019
57849385158293
...

result:

ok 100000 lines

Test #11:

score: 0
Accepted
time: 52ms
memory: 3600kb

input:

50 100000
60728 530697
83230 727339
45243 395375
271 2367
937 8187
571 4989
96761 845587
86457 755540
90323 789326
90399 789990
10594 92579
28403 248211
25357 221591
87772 767032
55670 486495
60282 526800
561 4901
982 8581
76641 669760
55342 483628
48873 427096
35548 310650
885 7732
366 3197
97922 8...

output:

3133482579349
7494810757936
4555523942199
7435663815990
4295642762189
4283159865903
7414897829567
3903222990230
2968892612466
2402291613912
7236198642831
5958918161447
5261989325962
8219650772200
8002405485131
1280272079456
2516194298124
6485543326094
5914337283589
3655130327670
8138120928303
562677...

result:

ok 100000 lines

Test #12:

score: 0
Accepted
time: 79ms
memory: 3808kb

input:

50 100000
752 7335
35936 355240
78116 773279
875 8560
37342 370817
828 8074
33846 336100
626 5445
637 6325
81715 811475
922 9138
644 6387
34748 345067
65805 653291
773 7676
95603 949353
26425 262405
22429 222731
298 700
56821 564207
55641 550825
70764 702726
83996 834127
76002 751937
809 8033
40212 ...

output:

7111801231201
3974877636421
5700005708999
3692431519429
8390243928314
4856596904186
8649578596588
7650211480686
1927659798764
9782548648155
8479708176408
9819016854150
8299811317590
5081730554339
7181513224616
7016657590948
4598429005570
7064239937890
1894397377944
9158923708950
9429673769511
640200...

result:

ok 100000 lines

Test #13:

score: 0
Accepted
time: 28ms
memory: 3528kb

input:

50 100000
170 4385
22940 593206
19334 497879
661 16919
36639 943136
680 16801
175 1933
24745 640044
630 16150
712 18184
25478 658858
5254 135883
593 13956
483 12493
53 1368
671 17337
30286 783365
67 1505
260 6724
30402 786351
735 16014
439 11183
774 20006
29857 772269
219 5646
33830 872043
545 13983...

output:

3091874714546
3799885716307
22913992421805
20781578026626
9696367215401
17079064022650
15266829005336
12716799226040
23731015553112
13150289026092
23125562879023
24082511231560
16442327860614
16710351460006
17377030170413
19889742758455
24143898823387
24579536189422
5664429089292
14123921926609
1188...

result:

ok 100000 lines

Test #14:

score: 0
Accepted
time: 55ms
memory: 3548kb

input:

50 100000
12872 40832
44877 152256
18222 62620
599 2058
858 2755
53 175
41873 143989
284 542
34220 117503
47602 163138
94093 323570
34385 118229
31383 107387
78203 268927
822 1974
21639 74215
21514 70710
88774 304816
5723 18494
48817 166227
44425 150859
62902 216253
2115 7273
92750 318953
23873 8113...

output:

972583843975
1500132979346
1351110512869
2651661013626
1567640546469
2636693130076
3140962697172
3005069633394
477801957885
586903286018
1414473226377
2838952488619
2913069760655
1247166415399
1800946440555
2219172514084
1420446731825
2282216730656
3263222752358
1419778877024
813957923046
3038297548...

result:

ok 100000 lines

Test #15:

score: 0
Accepted
time: 64ms
memory: 3560kb

input:

50 100000
94773 586021
45804 283087
43569 269460
139 655
197 1119
902 5573
802 4959
42193 257193
74590 461121
38503 237911
84775 524113
49698 307377
52359 323626
35421 218803
95936 592506
54169 334570
46135 282557
183 1005
551 3406
54011 332948
87634 538220
50995 315382
37376 231043
884 5457
23349 1...

output:

755841260191
1252231115949
1405433485836
5636840899775
5371897697677
929836987029
5411621528821
1818599573317
4388135038554
2603763733441
1441877300548
2168986680292
2713013963253
1914999688006
1574706928431
3938553667216
1627081727337
6008861962529
1650049686004
4494100602062
5096648478093
13687409...

result:

ok 100000 lines

Test #16:

score: 0
Accepted
time: 64ms
memory: 3836kb

input:

50 100000
58536 92555
71509 112933
94422 149184
63 95
80921 126185
38346 56105
44177 69746
45169 71178
298 216
63443 99936
29086 45990
96 149
27458 43407
613 960
97713 154500
44568 67713
32059 49616
28154 44516
89948 142226
14021 21007
31512 49609
77997 123329
33102 52326
252 215
525 821
656 1036
49...

output:

967335520356
420536402920
1435463142512
392084511433
248559288369
574427565134
457576915371
467459171705
1403009454418
796444398931
1554182290834
712925732496
1245546277351
503742189573
1218790613598
904312567895
1419278227552
677052246752
1421494165420
460905985499
1172552348687
1397589924025
10217...

result:

ok 100000 lines

Test #17:

score: 0
Accepted
time: 18ms
memory: 3464kb

input:

50 100000
711 556482
390 305114
867 678643
944 738915
74 57923
930 727957
570 445979
391 305787
748 585361
764 598020
831 650360
169 132173
76 59488
698 544664
313 244777
651 509380
599 468668
103 80604
513 401539
95 74178
837 655143
510 398949
501 391927
929 724184
852 662207
644 499916
148 114280
...

output:

341291679729397
617075776921034
700201758437376
361776436445975
388458558648002
190375047622892
303828220978374
162487530229052
335717680956704
559723583054536
270562627020771
180139099030638
280224653427881
665974688960031
339520224837471
403288881504977
634321672763127
329960069913508
741168221805...

result:

ok 100000 lines

Test #18:

score: 0
Accepted
time: 14ms
memory: 3532kb

input:

50 100000
485 820563
42 70656
115 194069
150 253782
195 329858
441 745495
91 152865
406 686649
64 108093
378 639263
45 74650
515 871320
40 67572
245 414505
544 920383
38 61352
234 392369
429 720920
99 167359
305 516023
36 57709
48 81120
149 251989
398 673368
354 598751
544 920367
97 164011
156 26373...

output:

755382111491744
455052074294535
215978329461273
310696344735984
681874069039009
1494798642374757
384442974232262
1302138309089245
318340266491334
298605803512438
1035525881221421
446514711614218
763555453424016
774472784434617
813815996116092
1391699784058989
1507669921072971
1354015656166509
145654...

result:

ok 100000 lines

Test #19:

score: 0
Accepted
time: 66ms
memory: 3904kb

input:

50 100000
39482 327363
50321 417234
89948 742261
78548 651222
89590 739193
917 7321
60596 502428
810 3245
45240 375103
57859 478730
32153 266594
279 2313
31490 261049
86976 718473
979 8117
80979 667235
926 7272
71753 594935
12528 103875
50887 421660
33863 276225
30453 252206
8765 72673
875 7161
5111...

output:

6731749684666
4032270244888
5411739551560
6235766874094
2959573939416
7555222434747
7601300014728
3029802304008
1361990123803
831309415291
5794354649203
7304426742458
8161406426143
4177197566973
5113584682224
7381834365117
924440745847
3259527057544
6436894464135
1068112692382
5379566411215
41586340...

result:

ok 100000 lines

Test #20:

score: 0
Accepted
time: 26ms
memory: 3464kb

input:

50 100000
629 18852
21 624
16899 506524
26864 805207
9735 291660
247 7396
18329 547068
135 3914
516 15464
953 28447
678 20313
676 20261
12106 362664
24000 719369
404 12094
449 13341
882 25449
433 12813
21451 642966
662 19824
25868 775352
18242 546779
531 15912
439 13150
15171 454717
253 7356
10215 3...

output:

23413687773033
18476097852457
19963586762695
20090731549076
28057785352574
3510628918610
15554493513836
29639521327529
27394152634369
21954906566336
11638298065365
21232403657767
24481543641333
20868550658398
21759813406058
7867980001126
24213221940257
14487616330936
11461290619175
24922151713274
15...

result:

ok 100000 lines