#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mxN = 1e5 + 5 , mxS = 2e3 + 5;
int n,s;
vector<pair<int,int>> bag[mxS];
ll dp[mxS];
int main(){
scanf("%d %d",&s,&n);
for(int i=1;i<=n;i++){
int v,w,k;
scanf("%d %d %d",&v,&w,&k);
bag[w].push_back({v , min(k , s/w)});
}
for(int w=1;w<=s;w++) sort(bag[w].begin() , bag[w].end() , greater<pair<int,int>>());
// for(int w=1;w<=s;w++){
// if(bag[w].empty()) continue;
// printf("w = %d : " , w);
// for(auto [v , k] : bag[w]) printf("%d %d , " , v , k);
// printf("\n");
// }
for(int w=1;w<=s;w++){
if(bag[w].empty()) continue;
int lim_k = s / w;
int curr = bag[w][0].second , idx = 0;
for(int k=1;k<=lim_k;k++){
for(int cap=s;cap>=w;cap--) dp[cap] = max(dp[cap] , dp[cap - w] + bag[w][idx].first);
if(k >= curr){
idx++;
curr += bag[w][idx].second;
if(idx>= int(bag[w].size())) break;
}
}
}
printf("%lld" , dp[s]);
return 0;
}
Compilation message
knapsack.cpp: In function 'int main()':
knapsack.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | scanf("%d %d",&s,&n);
| ~~~~~^~~~~~~~~~~~~~~
knapsack.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | scanf("%d %d %d",&v,&w,&k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
484 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
484 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
480 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
508 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
484 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
480 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
2 ms |
508 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
3 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
504 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
352 KB |
Output is correct |
30 |
Correct |
1 ms |
344 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
484 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
480 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
2 ms |
508 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
3 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
504 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
352 KB |
Output is correct |
30 |
Correct |
1 ms |
344 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
1 ms |
348 KB |
Output is correct |
35 |
Correct |
26 ms |
2516 KB |
Output is correct |
36 |
Correct |
31 ms |
2668 KB |
Output is correct |
37 |
Correct |
30 ms |
2308 KB |
Output is correct |
38 |
Correct |
26 ms |
2900 KB |
Output is correct |
39 |
Correct |
29 ms |
3464 KB |
Output is correct |
40 |
Correct |
54 ms |
3920 KB |
Output is correct |
41 |
Correct |
35 ms |
2908 KB |
Output is correct |
42 |
Correct |
36 ms |
2976 KB |
Output is correct |
43 |
Correct |
45 ms |
2832 KB |
Output is correct |
44 |
Correct |
45 ms |
2900 KB |
Output is correct |
45 |
Correct |
28 ms |
3664 KB |
Output is correct |
46 |
Correct |
25 ms |
3268 KB |
Output is correct |
47 |
Correct |
31 ms |
3664 KB |
Output is correct |
48 |
Correct |
36 ms |
3464 KB |
Output is correct |
49 |
Correct |
23 ms |
3556 KB |
Output is correct |
50 |
Correct |
43 ms |
3420 KB |
Output is correct |