#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair
int main() {
int maxWeight, N;
cin >> maxWeight >> N;
vector<vector<pi>> items(maxWeight + 1, vector<pi>());
for (int curW = 0; curW < N; curW++) {
int V, W, K;
cin >> V >> W >> K;
items[W].pb({ V, K });
}
for (int curW = 0; curW <= maxWeight; curW++) {
sort(all(items[curW]), greater<pi>());
}
int maxItems = 0;
for (int curW = 1; curW <= maxWeight; curW++) {
maxItems += maxWeight / curW;
}
vector<vi> dp(maxItems + 1, vi(maxWeight + 1, 0));
int numItems = 1;
for (int curW = 1; curW <= maxWeight; curW++) {
if (items[curW].size() == 0) {
continue;
}
int idx = 0;
int copies = items[curW][0].second;
for (int amt = 0; amt < maxWeight / curW; amt++) {
for (int cur = 1; cur <= maxWeight; cur++) {
dp[numItems][cur] = dp[numItems - 1][cur];
if (cur - curW >= 0) {
dp[numItems][cur] = max(dp[numItems][cur], dp[numItems - 1][cur - curW] + items[curW][idx].f);
}
}
numItems++;
copies--;
if (copies == 0) {
idx++;
if (idx >= items[curW].size()) {
break;
}
copies = items[curW][idx].s;
}
}
}
cout << dp[numItems - 1][maxWeight] << "\n";
}
Compilation message
knapsack.cpp: In function 'int main()':
knapsack.cpp:53:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | if (idx >= items[curW].size()) {
| ~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
44108 KB |
Output is correct |
2 |
Correct |
18 ms |
44056 KB |
Output is correct |
3 |
Correct |
18 ms |
44056 KB |
Output is correct |
4 |
Correct |
18 ms |
44100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
49 ms |
122316 KB |
Output is correct |
3 |
Correct |
47 ms |
122200 KB |
Output is correct |
4 |
Correct |
47 ms |
121860 KB |
Output is correct |
5 |
Correct |
53 ms |
121804 KB |
Output is correct |
6 |
Correct |
50 ms |
122372 KB |
Output is correct |
7 |
Correct |
50 ms |
122236 KB |
Output is correct |
8 |
Correct |
47 ms |
121876 KB |
Output is correct |
9 |
Correct |
48 ms |
121796 KB |
Output is correct |
10 |
Correct |
48 ms |
122180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
49 ms |
122316 KB |
Output is correct |
3 |
Correct |
47 ms |
122200 KB |
Output is correct |
4 |
Correct |
47 ms |
121860 KB |
Output is correct |
5 |
Correct |
53 ms |
121804 KB |
Output is correct |
6 |
Correct |
50 ms |
122372 KB |
Output is correct |
7 |
Correct |
50 ms |
122236 KB |
Output is correct |
8 |
Correct |
47 ms |
121876 KB |
Output is correct |
9 |
Correct |
48 ms |
121796 KB |
Output is correct |
10 |
Correct |
48 ms |
122180 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
52 ms |
122392 KB |
Output is correct |
13 |
Correct |
47 ms |
122244 KB |
Output is correct |
14 |
Correct |
47 ms |
122304 KB |
Output is correct |
15 |
Correct |
50 ms |
121804 KB |
Output is correct |
16 |
Correct |
48 ms |
122236 KB |
Output is correct |
17 |
Correct |
51 ms |
121884 KB |
Output is correct |
18 |
Correct |
49 ms |
122180 KB |
Output is correct |
19 |
Correct |
48 ms |
122380 KB |
Output is correct |
20 |
Correct |
47 ms |
121876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
44108 KB |
Output is correct |
2 |
Correct |
18 ms |
44056 KB |
Output is correct |
3 |
Correct |
18 ms |
44056 KB |
Output is correct |
4 |
Correct |
18 ms |
44100 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
49 ms |
122316 KB |
Output is correct |
7 |
Correct |
47 ms |
122200 KB |
Output is correct |
8 |
Correct |
47 ms |
121860 KB |
Output is correct |
9 |
Correct |
53 ms |
121804 KB |
Output is correct |
10 |
Correct |
50 ms |
122372 KB |
Output is correct |
11 |
Correct |
50 ms |
122236 KB |
Output is correct |
12 |
Correct |
47 ms |
121876 KB |
Output is correct |
13 |
Correct |
48 ms |
121796 KB |
Output is correct |
14 |
Correct |
48 ms |
122180 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
52 ms |
122392 KB |
Output is correct |
17 |
Correct |
47 ms |
122244 KB |
Output is correct |
18 |
Correct |
47 ms |
122304 KB |
Output is correct |
19 |
Correct |
50 ms |
121804 KB |
Output is correct |
20 |
Correct |
48 ms |
122236 KB |
Output is correct |
21 |
Correct |
51 ms |
121884 KB |
Output is correct |
22 |
Correct |
49 ms |
122180 KB |
Output is correct |
23 |
Correct |
48 ms |
122380 KB |
Output is correct |
24 |
Correct |
47 ms |
121876 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
57 ms |
122196 KB |
Output is correct |
27 |
Correct |
47 ms |
122308 KB |
Output is correct |
28 |
Correct |
49 ms |
122180 KB |
Output is correct |
29 |
Correct |
60 ms |
122204 KB |
Output is correct |
30 |
Correct |
49 ms |
122164 KB |
Output is correct |
31 |
Correct |
47 ms |
122152 KB |
Output is correct |
32 |
Correct |
47 ms |
122232 KB |
Output is correct |
33 |
Correct |
49 ms |
121828 KB |
Output is correct |
34 |
Correct |
50 ms |
122256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
44108 KB |
Output is correct |
2 |
Correct |
18 ms |
44056 KB |
Output is correct |
3 |
Correct |
18 ms |
44056 KB |
Output is correct |
4 |
Correct |
18 ms |
44100 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
49 ms |
122316 KB |
Output is correct |
7 |
Correct |
47 ms |
122200 KB |
Output is correct |
8 |
Correct |
47 ms |
121860 KB |
Output is correct |
9 |
Correct |
53 ms |
121804 KB |
Output is correct |
10 |
Correct |
50 ms |
122372 KB |
Output is correct |
11 |
Correct |
50 ms |
122236 KB |
Output is correct |
12 |
Correct |
47 ms |
121876 KB |
Output is correct |
13 |
Correct |
48 ms |
121796 KB |
Output is correct |
14 |
Correct |
48 ms |
122180 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
52 ms |
122392 KB |
Output is correct |
17 |
Correct |
47 ms |
122244 KB |
Output is correct |
18 |
Correct |
47 ms |
122304 KB |
Output is correct |
19 |
Correct |
50 ms |
121804 KB |
Output is correct |
20 |
Correct |
48 ms |
122236 KB |
Output is correct |
21 |
Correct |
51 ms |
121884 KB |
Output is correct |
22 |
Correct |
49 ms |
122180 KB |
Output is correct |
23 |
Correct |
48 ms |
122380 KB |
Output is correct |
24 |
Correct |
47 ms |
121876 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
57 ms |
122196 KB |
Output is correct |
27 |
Correct |
47 ms |
122308 KB |
Output is correct |
28 |
Correct |
49 ms |
122180 KB |
Output is correct |
29 |
Correct |
60 ms |
122204 KB |
Output is correct |
30 |
Correct |
49 ms |
122164 KB |
Output is correct |
31 |
Correct |
47 ms |
122152 KB |
Output is correct |
32 |
Correct |
47 ms |
122232 KB |
Output is correct |
33 |
Correct |
49 ms |
121828 KB |
Output is correct |
34 |
Correct |
50 ms |
122256 KB |
Output is correct |
35 |
Correct |
81 ms |
2288 KB |
Output is correct |
36 |
Correct |
120 ms |
124236 KB |
Output is correct |
37 |
Correct |
116 ms |
124212 KB |
Output is correct |
38 |
Correct |
125 ms |
124464 KB |
Output is correct |
39 |
Correct |
153 ms |
124804 KB |
Output is correct |
40 |
Correct |
170 ms |
125516 KB |
Output is correct |
41 |
Correct |
148 ms |
124744 KB |
Output is correct |
42 |
Correct |
140 ms |
124656 KB |
Output is correct |
43 |
Correct |
149 ms |
124868 KB |
Output is correct |
44 |
Correct |
147 ms |
124344 KB |
Output is correct |
45 |
Correct |
143 ms |
125736 KB |
Output is correct |
46 |
Correct |
137 ms |
125060 KB |
Output is correct |
47 |
Correct |
143 ms |
125728 KB |
Output is correct |
48 |
Correct |
163 ms |
125632 KB |
Output is correct |
49 |
Correct |
131 ms |
125252 KB |
Output is correct |
50 |
Correct |
155 ms |
125244 KB |
Output is correct |