QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#665075#7739. KnapsackchatokjuniorTL 32ms590776kbC++231.0kb2024-10-22 02:12:022024-10-22 02:12:02

Judging History

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

  • [2024-10-22 02:12:02]
  • 评测
  • 测评结果:TL
  • 用时:32ms
  • 内存:590776kb
  • [2024-10-22 02:12:02]
  • 提交

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...

output:


result: