#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
//const int MOD=1e9+7;
//typedef pair<ll,ll>Point;
//typedef pair<ll,ll>Line;
//#define x first
//#define y second
ll knapsack(vector<pair<int,int>>arr,int s){ // (weight, reward)
vector<vector<ll>>dp(arr.size()+1,vector<ll>(s+1)); // dp[i][j] = if we take first i elements, how much can we take with j space left
for(int i=1;i<=arr.size();i++){
for(int j=0;j<=s;j++){
dp[i][j]=dp[i-1][j];
if(j-arr[i-1].first>=0){
dp[i][j]=max(dp[i][j],dp[i-1][j-arr[i-1].first]+arr[i-1].second);
}
}
}
return dp[(int)arr.size()][s];
}
void solve(){
int s,n;
cin>>s>>n;
vector<vector<pair<int,int>>>arr(2001);
for(int i=0;i<n;i++){
int w,r,c;
cin>>r>>w>>c;
arr[w].emplace_back(r,c);
}
vector<pair<int,int>>arr2;
for(int i=1;i<2001;i++){
sort(arr[i].begin(),arr[i].end());
reverse(arr[i].begin(),arr[i].end());
int rem=s/i;
for(auto j:arr[i]){
while(j.second&&rem){
arr2.emplace_back(i,j.first);
j.second--;
rem--;
}
if(rem==0)
break;
}
}
cout<<knapsack(arr2,s)<<"\n";
}
int main(){
ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
//freopen("bank.in","r",stdin);freopen("bank.out","w",stdout);
int t=1;//cin>>t;
while(t--)solve();
return 0;
}
/*
15 5
4 12 1
2 1 1
10 4 1
1 1 1
2 2 1
15
20 3
5000 15 1
100 1 3
50 1 4
5400
*/
Compilation message
knapsack.cpp: In function 'll knapsack(std::vector<std::pair<int, int> >, int)':
knapsack.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int i=1;i<=arr.size();i++){
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
1628 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
1884 KB |
Output is correct |
3 |
Correct |
1 ms |
1884 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
600 KB |
Output is correct |
6 |
Correct |
2 ms |
2136 KB |
Output is correct |
7 |
Correct |
1 ms |
1884 KB |
Output is correct |
8 |
Correct |
1 ms |
1884 KB |
Output is correct |
9 |
Correct |
1 ms |
1884 KB |
Output is correct |
10 |
Correct |
1 ms |
1884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
1884 KB |
Output is correct |
3 |
Correct |
1 ms |
1884 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
600 KB |
Output is correct |
6 |
Correct |
2 ms |
2136 KB |
Output is correct |
7 |
Correct |
1 ms |
1884 KB |
Output is correct |
8 |
Correct |
1 ms |
1884 KB |
Output is correct |
9 |
Correct |
1 ms |
1884 KB |
Output is correct |
10 |
Correct |
1 ms |
1884 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
9 ms |
15708 KB |
Output is correct |
13 |
Correct |
1 ms |
1884 KB |
Output is correct |
14 |
Correct |
0 ms |
604 KB |
Output is correct |
15 |
Correct |
0 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
3932 KB |
Output is correct |
17 |
Correct |
1 ms |
1884 KB |
Output is correct |
18 |
Correct |
1 ms |
2396 KB |
Output is correct |
19 |
Correct |
3 ms |
3676 KB |
Output is correct |
20 |
Correct |
2 ms |
3420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
1628 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
1884 KB |
Output is correct |
7 |
Correct |
1 ms |
1884 KB |
Output is correct |
8 |
Correct |
0 ms |
604 KB |
Output is correct |
9 |
Correct |
0 ms |
600 KB |
Output is correct |
10 |
Correct |
2 ms |
2136 KB |
Output is correct |
11 |
Correct |
1 ms |
1884 KB |
Output is correct |
12 |
Correct |
1 ms |
1884 KB |
Output is correct |
13 |
Correct |
1 ms |
1884 KB |
Output is correct |
14 |
Correct |
1 ms |
1884 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
9 ms |
15708 KB |
Output is correct |
17 |
Correct |
1 ms |
1884 KB |
Output is correct |
18 |
Correct |
0 ms |
604 KB |
Output is correct |
19 |
Correct |
0 ms |
604 KB |
Output is correct |
20 |
Correct |
2 ms |
3932 KB |
Output is correct |
21 |
Correct |
1 ms |
1884 KB |
Output is correct |
22 |
Correct |
1 ms |
2396 KB |
Output is correct |
23 |
Correct |
3 ms |
3676 KB |
Output is correct |
24 |
Correct |
2 ms |
3420 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
16 ms |
31772 KB |
Output is correct |
27 |
Correct |
1 ms |
1884 KB |
Output is correct |
28 |
Correct |
1 ms |
600 KB |
Output is correct |
29 |
Correct |
0 ms |
604 KB |
Output is correct |
30 |
Correct |
6 ms |
10736 KB |
Output is correct |
31 |
Correct |
1 ms |
2076 KB |
Output is correct |
32 |
Correct |
1 ms |
2140 KB |
Output is correct |
33 |
Correct |
2 ms |
3164 KB |
Output is correct |
34 |
Correct |
2 ms |
4444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
1628 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
1884 KB |
Output is correct |
7 |
Correct |
1 ms |
1884 KB |
Output is correct |
8 |
Correct |
0 ms |
604 KB |
Output is correct |
9 |
Correct |
0 ms |
600 KB |
Output is correct |
10 |
Correct |
2 ms |
2136 KB |
Output is correct |
11 |
Correct |
1 ms |
1884 KB |
Output is correct |
12 |
Correct |
1 ms |
1884 KB |
Output is correct |
13 |
Correct |
1 ms |
1884 KB |
Output is correct |
14 |
Correct |
1 ms |
1884 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
9 ms |
15708 KB |
Output is correct |
17 |
Correct |
1 ms |
1884 KB |
Output is correct |
18 |
Correct |
0 ms |
604 KB |
Output is correct |
19 |
Correct |
0 ms |
604 KB |
Output is correct |
20 |
Correct |
2 ms |
3932 KB |
Output is correct |
21 |
Correct |
1 ms |
1884 KB |
Output is correct |
22 |
Correct |
1 ms |
2396 KB |
Output is correct |
23 |
Correct |
3 ms |
3676 KB |
Output is correct |
24 |
Correct |
2 ms |
3420 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
16 ms |
31772 KB |
Output is correct |
27 |
Correct |
1 ms |
1884 KB |
Output is correct |
28 |
Correct |
1 ms |
600 KB |
Output is correct |
29 |
Correct |
0 ms |
604 KB |
Output is correct |
30 |
Correct |
6 ms |
10736 KB |
Output is correct |
31 |
Correct |
1 ms |
2076 KB |
Output is correct |
32 |
Correct |
1 ms |
2140 KB |
Output is correct |
33 |
Correct |
2 ms |
3164 KB |
Output is correct |
34 |
Correct |
2 ms |
4444 KB |
Output is correct |
35 |
Correct |
20 ms |
1744 KB |
Output is correct |
36 |
Correct |
43 ms |
33996 KB |
Output is correct |
37 |
Correct |
40 ms |
33788 KB |
Output is correct |
38 |
Correct |
22 ms |
2900 KB |
Output is correct |
39 |
Correct |
27 ms |
3532 KB |
Output is correct |
40 |
Correct |
160 ms |
247260 KB |
Output is correct |
41 |
Correct |
88 ms |
144720 KB |
Output is correct |
42 |
Correct |
113 ms |
155472 KB |
Output is correct |
43 |
Correct |
143 ms |
246812 KB |
Output is correct |
44 |
Correct |
140 ms |
245588 KB |
Output is correct |
45 |
Correct |
33 ms |
21068 KB |
Output is correct |
46 |
Correct |
26 ms |
3220 KB |
Output is correct |
47 |
Correct |
51 ms |
42580 KB |
Output is correct |
48 |
Correct |
79 ms |
114592 KB |
Output is correct |
49 |
Correct |
24 ms |
5208 KB |
Output is correct |
50 |
Correct |
107 ms |
144304 KB |
Output is correct |