QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #689893 | #7739. Knapsack | i_love_qingyu# | WA | 12ms | 44016kb | C++20 | 1.0kb | 2024-10-30 19:05:40 | 2024-10-30 19:05:42 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
/*struct node{
long long int w;
int id;
bool operator <(const node &x)const{
return x.w<w;
}
};
priority_queue<node>q[40004];*/
long long v[40004],w[40004],dp[10004][5003];
//priority_queue<int > p;
int main()
{
int n,m,k;
long long ans=0;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=m;j>=1;j--){
for(int x=k;x>=1;x--)
if(j>=v[i])
dp[j][x]=max(dp[j][x-1]+w[i],max(dp[j][x],dp[j-v[i]][x]+w[i]));
else
dp[j][x]=max(dp[j][x-1]+w[i],dp[j][x]);
if(j>=v[i])
dp[j][0]=max(dp[j-v[i]][0]+w[i],dp[j][0]);
}
for(int i=0;i<=m;i++)
for(int x=0;x<=k;x++)
ans=max(ans,dp[i][x]);
cout<<ans;
return 0;
}
/*
5 13 2
5 16
5 28
7 44
8 15
8 41
4 10 1
9 10
10 1
3 5
5 20
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5772kb
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: 3676kb
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: 3804kb
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: 3944kb
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: 0ms
memory: 5540kb
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: 17964kb
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: 12ms
memory: 44016kb
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: -100
Wrong Answer
time: 1ms
memory: 5900kb
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:
44733062110
result:
wrong answer 1st numbers differ - expected: '44747553879', found: '44733062110'