#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <cmath>
#include <algorithm>
#include <array>
#include <set>
#include <climits>
#include <map>
#include <memory>
#include <string>
#include <deque>
#include <queue>
#include <stack>
using namespace std;
#define input "knapsack.in"
#define output "knapsack.out"
#define int long long
typedef pair<int, int> pii;
int S, n;
vector<vector<pii>> items;//grouped by weight
vector<pii> all_items;//each weight can have up to S pounds in this vector, making it SlogS
vector<int> dp;//for each weight, what is the maximum value possible?
int res=0;
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
//freopen(input, "r", stdin);
//freopen(output, "w", stdout);
cin >> S >> n;
items.resize(S+1);
dp.resize(S+1, 0);
for (int i=0;i<n;i++) {
int val, wt, amt;
cin >> val >> wt >> amt;
items[wt].push_back({val, amt});
}
for (int s=1;s<=S;s++) {
sort(items[s].begin(), items[s].end(), [](pii& a, pii& b) -> bool {
return a.first>b.first;
});
}
all_items.reserve(S*S);
for (int s=1;s<=S;s++) {
int curr_weight=0;
for (pii item: items[s]) {
for (int k=0;k<item.second;k++) {
curr_weight+=s;
if (curr_weight>S) break;
all_items.push_back({s, item.first});
}
if (curr_weight>S) break;
}
}
for (pii item: all_items) {
//out << item.first << ' ' << item.second << endl;
for (int s=S-1;s>=0;s--) {
if (item.first+s>S) continue;
dp[item.first+s]=max(dp[item.first+s], item.second+dp[s]);
res=max(res, dp[item.first+s]);
}
}
//for (int s=0;s<=S;s++) cout << dp[s] << ' '; cout << endl;
//cout << all_items.size() << endl;
cout << res << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
308 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
308 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
8 ms |
316 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
2 ms |
308 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
2 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
308 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
308 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
8 ms |
316 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
308 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
2 ms |
332 KB |
Output is correct |
24 |
Correct |
2 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
16 ms |
424 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
5 ms |
400 KB |
Output is correct |
31 |
Correct |
1 ms |
312 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
2 ms |
332 KB |
Output is correct |
34 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
308 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
308 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
8 ms |
316 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
308 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
2 ms |
332 KB |
Output is correct |
24 |
Correct |
2 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
16 ms |
424 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
5 ms |
400 KB |
Output is correct |
31 |
Correct |
1 ms |
312 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
2 ms |
332 KB |
Output is correct |
34 |
Correct |
2 ms |
332 KB |
Output is correct |
35 |
Correct |
42 ms |
2652 KB |
Output is correct |
36 |
Correct |
54 ms |
3520 KB |
Output is correct |
37 |
Correct |
49 ms |
3404 KB |
Output is correct |
38 |
Correct |
37 ms |
3708 KB |
Output is correct |
39 |
Correct |
45 ms |
4352 KB |
Output is correct |
40 |
Correct |
154 ms |
5008 KB |
Output is correct |
41 |
Correct |
102 ms |
4036 KB |
Output is correct |
42 |
Correct |
101 ms |
4148 KB |
Output is correct |
43 |
Correct |
146 ms |
4268 KB |
Output is correct |
44 |
Correct |
149 ms |
4200 KB |
Output is correct |
45 |
Correct |
49 ms |
4800 KB |
Output is correct |
46 |
Correct |
37 ms |
4024 KB |
Output is correct |
47 |
Correct |
60 ms |
5024 KB |
Output is correct |
48 |
Correct |
97 ms |
4812 KB |
Output is correct |
49 |
Correct |
35 ms |
4548 KB |
Output is correct |
50 |
Correct |
110 ms |
4388 KB |
Output is correct |