QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #283347 | #5690. 背包 | YeahPotato# | AC ✓ | 73ms | 5076kb | C++14 | 796b | 2023-12-14 15:10:01 | 2023-12-14 15:10:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5; const long long NI = - 8e18;
int n, q, v[N], c[N], t, vis[N]; long long f[N], V;
int main() {
cin >> n >> q;
for (int i=1; i<=n; i++) {
scanf ("%d%d", &v[i], &c[i]);
if (1ll * c[i] * v[t] >= 1ll * c[t] * v[i])
t = i;
} swap(v[1], v[t]), swap(c[1], c[t]);
for (int i=1; i<v[1]; i++)
f[i] = NI;
for (int i=2; i<=n; i++) {
for (int j=0; j<v[1]; j++)
vis[j] = 0;
for (int j=0; j<v[1]; j++) if (! vis[j])
for (int u=j; vis[u]^2; vis[u]++, u=(u+v[i])%v[1])
if (f[u] ^ NI)
f[(u+v[i])%v[1]] = max(f[(u+v[i])%v[1]], f[u] + c[i] - 1ll * (u + v[i]) / v[1] * c[1]);
}
while (q --)
scanf ("%lld", &V), printf ("%lld\n", f[V%v[1]] ^ NI ? f[V%v[1]] + 1ll * V / v[1] * c[1] : - 1);
}
詳細信息
Test #1:
score: 100
Accepted
time: 16ms
memory: 3692kb
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: 12ms
memory: 3880kb
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: 16ms
memory: 3832kb
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: 13ms
memory: 3888kb
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: 22ms
memory: 3920kb
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: 63ms
memory: 5076kb
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: 65ms
memory: 4928kb
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: 33ms
memory: 4280kb
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: 12ms
memory: 3804kb
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: 20ms
memory: 4012kb
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: 51ms
memory: 4452kb
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: 73ms
memory: 4956kb
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: 33ms
memory: 4160kb
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: 52ms
memory: 4368kb
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: 59ms
memory: 4544kb
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: 62ms
memory: 4684kb
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: 7ms
memory: 3912kb
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: 16ms
memory: 3876kb
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: 59ms
memory: 4636kb
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: 29ms
memory: 3972kb
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