QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#738527 | #7739. Knapsack | highkj | TL | 771ms | 238660kb | C++14 | 2.2kb | 2024-11-12 19:17:20 | 2024-11-12 19:17:21 |
Judging History
answer
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define int long long
#define fire signed
#define il inline
template<class T> il void print(T x) {
if(x<0) printf("-"),x=-x;
if (x > 9) print(x / 10);
putchar(x % 10 + '0');
}
const int bufsize = 230005;
char buf[bufsize], *f1, *f2;
#define getchar() (f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++)
template<class T> il void in(T &x) {
x = 0; char ch = getchar();
int f = 1;
while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
x *= f;
}
int T=1;
const int N=5e3+10,M=1e4+10;
int f[N][M];
struct node{
int v,w;
friend bool operator<(const node&a,const node&b) {
return a.v<b.v;
}
}s[N];
int n,m,k;
int vis[N],dis[N];
multiset<int>se;
//priority_queue<int,vector<int>,greater<int>>q;
void solve() {
in(n),in(m),in(k);
rep(i,1,n) in(s[i].v),in(s[i].w);
sort(s+1,s+1+n);
rep(i,1,n) {
rep(j,0,m) {
if(j<s[i].v) f[i][j]=f[i-1][j];
else f[i][j]=max(f[i-1][j],f[i-1][j-s[i].v]+s[i].w);
}
}
int ss=0;
// rep1(i,n,1) {
// dis[i]=ss;
// while(q.size()>=k&&q.top()<s[i].w) ss-=q.top(),q.pop();
// q.push(s[i].w);
// ss+=s[i].w;
// }
int res=false;
rep(i,1,n) {
se.clear();
rep(j,1,n) vis[j]=false;
int x=i,mm=m;
while(x) {
if(f[x][mm]==f[x-1][mm-s[x].v]+s[x].w) {
vis[x]=1;
mm-=s[x].v;
}
x--;
}
rep(j,1,n) {
if(!vis[j]) {
se.insert(s[j].w);
}
}
auto it=se.end();
it--;
int kk=k;
int dis=0;
for(;;it--) {
dis+=*it;
kk--;
if(!kk||it==se.begin()) break;
}
res=max(res,dis+f[i][m]);
}
printf("%lld\n",res);
}
fire main() {
// freopen("knapsack.in","r",stdin);
// freopen("knapsack.out","w",stdout);
while(T--) {
solve();
}
return false;
}
/*
5 5 1
4 13627
3 17167
1 14354
2 8880
2 12354
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3880kb
input:
4 10 1 9 10 10 1 3 5 5 20
output:
35
result:
ok 1 number(s): "35"
Test #2:
score: 0
Accepted
time: 0ms
memory: 5900kb
input:
5 13 2 5 16 5 28 7 44 8 15 8 41
output:
129
result:
ok 1 number(s): "129"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
10 50 1 44 182173741 38 163268500 36 114173760 30 521894533 25 89514235 12 516184197 42 971377551 35 28242326 31 480227821 31 388523197
output:
2009456281
result:
ok 1 number(s): "2009456281"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
10 100 3 23 51015869 9 981426050 76 243762017 64 128189636 4 718411601 48 250140255 17 340478117 68 262055220 40 370503079 4 547232664
output:
3765024872
result:
ok 1 number(s): "3765024872"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5948kb
input:
10 500 10 430 981427684 100 458631577 32 453298334 393 716958962 82 120486064 393 561149128 182 518807793 293 950335710 332 159193263 331 280711850
output:
5201000365
result:
ok 1 number(s): "5201000365"
Test #6:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
10 3000 10 1325 563890842 2007 190665722 1393 874490922 548 279594682 1380 155046921 2666 894516819 770 740325614 2735 643777488 2451 754155860 1068 138544189
output:
5235009059
result:
ok 1 number(s): "5235009059"
Test #7:
score: 0
Accepted
time: 0ms
memory: 4572kb
input:
10 10000 5 108 735534045 6250 87364128 3071 66920092 9343 555321302 9070 759896065 9843 146885261 3083 364637443 7088 370871572 7802 754417134 3125 697204945
output:
4451687859
result:
ok 1 number(s): "4451687859"
Test #8:
score: 0
Accepted
time: 0ms
memory: 12012kb
input:
100 50 61 24 517916473 33 497071404 40 343150837 13 559776223 2 941245278 27 987936903 7 403293890 26 68412861 28 683505315 6 173482637 31 220799032 29 815472376 42 426462445 25 470177395 43 818534622 26 137556071 15 308105056 27 745044655 28 309413241 11 61130780 36 963194467 19 701095156 5 9347020...
output:
44747553879
result:
ok 1 number(s): "44747553879"
Test #9:
score: 0
Accepted
time: 2ms
memory: 12064kb
input:
100 100 42 6 774586597 36 576227741 25 257737545 64 559313526 24 371408966 47 803303316 73 342479452 100 619687258 73 682542576 71 182579788 61 354270154 74 30869398 23 995859349 88 255983493 48 334287458 17 13677067 8 441554725 24 934072639 85 610681655 67 327543259 60 697383634 99 320640445 50 974...
output:
37584168931
result:
ok 1 number(s): "37584168931"
Test #10:
score: 0
Accepted
time: 0ms
memory: 12204kb
input:
100 500 69 117 850222604 135 908209075 281 762241158 193 853115556 202 773483428 88 819344894 37 520809128 225 453191940 252 471232760 298 621091678 378 269475999 19 530190234 459 143203529 477 500583846 446 989780043 50 655756632 321 345085464 423 47668454 132 218063309 325 62856046 474 485855270 1...
output:
42850231504
result:
ok 1 number(s): "42850231504"
Test #11:
score: 0
Accepted
time: 0ms
memory: 12276kb
input:
100 3000 11 2229 113662521 1085 957207016 2571 864419576 2103 102031619 1086 208274995 2005 887504188 2305 803801229 2933 316528833 188 551740507 2720 393827507 2514 955559466 1772 749230500 2676 744768311 2499 772159519 1989 848103925 322 484923680 1757 619590795 571 247505048 1094 438346067 339 99...
output:
17333176908
result:
ok 1 number(s): "17333176908"
Test #12:
score: 0
Accepted
time: 0ms
memory: 12636kb
input:
100 10000 79 7606 40784641 9074 752695754 1153 594817340 9411 584292898 2132 533306184 2666 184228160 2417 356339298 9689 241354004 4927 287380554 7178 158913616 1095 172127175 1688 175994092 4105 75848992 1380 273029283 8421 35148963 432 256969077 5939 82792225 647 500031012 2795 65555568 3395 7706...
output:
44371890318
result:
ok 1 number(s): "44371890318"
Test #13:
score: 0
Accepted
time: 7ms
memory: 42880kb
input:
500 50 126 3 136023068 13 869807356 14 472367566 28 50725598 25 45069923 5 147985467 37 720797915 17 90311040 19 873648042 38 796138954 3 966881081 40 132652908 31 585596518 39 352737389 29 876373760 41 512453383 19 805025356 14 710658601 18 403371907 36 854558198 32 179695697 45 775294020 9 1462316...
output:
124994976191
result:
ok 1 number(s): "124994976191"
Test #14:
score: 0
Accepted
time: 7ms
memory: 42812kb
input:
500 100 98 69 129626760 5 449978106 61 989261186 72 638069575 26 280608378 52 685908155 81 932855739 82 82350114 21 792779442 77 493204907 56 830543473 59 105028460 89 731643951 16 264908763 29 925524933 44 662702166 98 466470962 79 202167196 63 116753433 24 790841938 83 993709118 27 951733632 53 41...
output:
103191714648
result:
ok 1 number(s): "103191714648"
Test #15:
score: 0
Accepted
time: 7ms
memory: 42900kb
input:
500 500 100 380 60038575 204 222150928 205 758606015 5 931871605 405 977650137 493 996917028 41 111185415 303 915854795 412 581469626 95 931716797 480 745749318 16 749573487 217 878988131 193 364284925 27 435793326 481 9814435 314 959936294 375 315763011 305 724135087 290 231187429 197 487213458 357...
output:
107219972338
result:
ok 1 number(s): "107219972338"
Test #16:
score: 0
Accepted
time: 8ms
memory: 42976kb
input:
500 3000 155 885 618166135 1814 400752150 649 826302551 2748 853231980 1650 386604671 30 721008870 2484 887458709 1852 755040724 2313 171979057 1769 893148343 342 397870943 549 848606662 1374 960069408 932 119271788 2006 46601960 2622 893486791 2703 521939745 2133 687850539 1808 931850407 1569 10566...
output:
150198202618
result:
ok 1 number(s): "150198202618"
Test #17:
score: 0
Accepted
time: 11ms
memory: 44616kb
input:
500 10000 39 2164 103861995 3931 307468016 3010 393436072 3416 653030414 6970 794867887 1656 84454065 2169 732024599 6555 453581890 7342 410350010 3201 783977518 4349 922318777 6290 401288294 5183 135437558 8855 659116512 3520 255820440 1262 608543507 496 19150219 2425 358615167 6883 685038845 8879 ...
output:
54344848517
result:
ok 1 number(s): "54344848517"
Test #18:
score: 0
Accepted
time: 35ms
memory: 81808kb
input:
1000 50 796 15 386711393 14 946648902 38 652093661 13 136124305 14 299275346 23 686324157 20 405295225 12 571269091 49 850320620 23 513862466 13 625703085 4 730549435 17 302756512 38 93155670 19 285511180 15 887672509 39 377740062 13 507552700 23 511922533 41 365183175 15 207169111 16 195211892 18 2...
output:
467973714946
result:
ok 1 number(s): "467973714946"
Test #19:
score: 0
Accepted
time: 33ms
memory: 81908kb
input:
1000 100 416 18 324358277 17 197544843 11 247666199 6 821941951 33 274893936 90 501323389 7 405955067 6 587405899 13 39935735 22 292638914 15 836533241 89 878937103 55 551121000 24 815495796 60 539203840 19 916500680 83 626606672 36 777244403 65 816148796 93 601676404 27 114182523 38 509405915 4 545...
output:
350454528075
result:
ok 1 number(s): "350454528075"
Test #20:
score: 0
Accepted
time: 35ms
memory: 81932kb
input:
1000 500 862 429 694961580 8 969717665 267 457202516 235 820776685 408 826711502 27 252523751 72 584284743 27 420910581 192 418560512 449 731150804 440 751739086 438 673225235 382 843689373 109 60096150 257 194696425 352 263612948 295 120072003 435 745616026 312 718497746 51 336989191 444 902654159 ...
output:
492713511906
result:
ok 1 number(s): "492713511906"
Test #21:
score: 0
Accepted
time: 39ms
memory: 81884kb
input:
1000 3000 351 727 8847709 2613 622538643 1461 97349529 1467 131003214 1043 126909307 532 219814384 2830 650278892 534 187011265 1312 789736632 1773 150503473 2766 702593294 1351 942888530 1656 764929540 2760 688345433 2131 310426897 1623 689276961 2098 193762961 2863 772562087 489 210523205 1687 791...
output:
317718205329
result:
ok 1 number(s): "317718205329"
Test #22:
score: 0
Accepted
time: 52ms
memory: 83552kb
input:
1000 10000 778 8901 374587545 7728 686705536 8090 632699030 8973 846089348 3693 855315786 8280 466401395 3762 691477129 7041 299407306 1348 72339995 266 48085564 6096 845178428 3340 512295215 9113 834760223 7761 585397824 4738 188388966 6971 458993083 3511 658239404 7788 959071523 5940 499882747 958...
output:
473643556169
result:
ok 1 number(s): "473643556169"
Test #23:
score: 0
Accepted
time: 668ms
memory: 100320kb
input:
3000 50 270 45 491619379 46 456136181 6 150276090 15 307922938 22 476230253 31 627626576 18 552999720 4 450084166 26 273018445 24 169175025 16 656547585 5 340241062 46 390744556 48 670230402 6 786162621 28 709925602 32 537681828 46 789083627 10 264958422 20 154381571 24 560364557 30 790662742 17 502...
output:
290860604546
result:
ok 1 number(s): "290860604546"
Test #24:
score: 0
Accepted
time: 668ms
memory: 126052kb
input:
3000 100 1090 95 929126436 78 344445858 98 596187078 81 402574836 60 159026070 98 213043026 1 447783807 58 731790292 68 365118050 47 337266628 37 702913172 29 76108832 3 526350941 1 914180379 68 211064953 69 603459740 8 77781147 69 849933501 74 430480358 60 232768589 11 51843442 56 346787151 100 879...
output:
924830589780
result:
ok 1 number(s): "924830589780"
Test #25:
score: 0
Accepted
time: 640ms
memory: 134576kb
input:
3000 500 459 405 4762442 77 116618680 254 805723396 206 846119970 138 415876340 143 374308795 65 921080779 391 420070782 255 153808234 366 775778518 354 323151721 474 575429668 231 378727825 178 13556540 265 426366050 206 395282408 121 276279182 268 113272420 220 892637820 218 968081376 24 545347782...
output:
460875644145
result:
ok 1 number(s): "460875644145"
Test #26:
score: 0
Accepted
time: 684ms
memory: 180832kb
input:
3000 3000 1123 2006 392902738 1337 679829030 286 921787343 270 240243524 1758 110206510 2323 449831592 1610 263249990 2063 940608857 1872 351221360 2785 890423328 2200 930205448 2396 350502927 2195 439948015 1794 954001143 1225 568246284 1390 922613232 1729 734554054 752 126982613 2181 167748492 242...
output:
926856325003
result:
ok 1 number(s): "926856325003"
Test #27:
score: 0
Accepted
time: 771ms
memory: 238660kb
input:
3000 10000 2445 9916 60955521 1311 546281196 8271 450785814 3811 340452615 6033 10211620 7021 920120703 5451 129814122 5163 99511373 5958 811056057 2900 348514492 529 300995446 5984 886829548 6799 628556572 8875 909284688 6902 228353975 4150 707453233 2608 433754217 5158 506050856 8125 823984360 320...
output:
1452952580705
result:
ok 1 number(s): "1452952580705"
Test #28:
score: -100
Time Limit Exceeded
input:
5000 50 190 32 301560068 25 260590756 20 793682711 25 774688866 21 798409351 36 568928995 16 140895703 49 33931946 8 550492078 29 119454880 7 247200596 2 949932689 29 38541113 4 807113645 50 581781359 41 386954504 25 697623595 18 775647258 42 17994312 48 533514559 37 208527299 44 681080887 16 176062...