QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#665075 | #7739. Knapsack | chatokjunior | TL | 32ms | 590776kb | C++23 | 1.0kb | 2024-10-22 02:12:02 | 2024-10-22 02:12:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define e "\n"
#define f first
#define s second
#define ll long long
#define pb push_back
#define pi (3.141592653589)
#define V vector<long long>
#define all(v) v.begin(), v.end()
#define fr(suru,ses) for(int i=suru;i<ses;i++)
const int N=5e3;
const int M=1e4;
ll dp[N+7][M+N+7];
ll n,w,k;
vector<pair<ll,ll>>v;
ll recur(ll i,ll c){
ll ans=0;
if(i==n || c==0)return ans;
if(c>w){
ans=dp[i][c]=max(recur(i+1,c-1)+v[i].s,recur(i+1,c));
}else {
ans=recur(i+1,c);
if(v[i].f<=c)ans=max(ans,recur(i+1,c-v[i].f)+v[i].s);
dp[i][c]=ans;
}
return ans;
}
void solve(int t,int tc){
memset(dp,-1,sizeof(dp));
cin>>n>>w>>k;
v.resize(n);
for(int i=0;i<n;i++)cin>>v[i].f>>v[i].s;
sort(v.rbegin(),v.rend());
cout<<recur(0,w+k)<<e;
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1; //cin>>t;
fr(1,t+1)solve(i,t);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 15ms
memory: 590720kb
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: 32ms
memory: 590624kb
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: 11ms
memory: 590716kb
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: 19ms
memory: 590764kb
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: 15ms
memory: 590776kb
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: 31ms
memory: 590688kb
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: 15ms
memory: 590700kb
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
Time Limit Exceeded
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...