#include <algorithm>
#include <iostream>
#include <limits>
#include <unordered_map>
#include <vector>
struct item {
size_t value = 0;
size_t count = 0;
};
inline bool cmp_most_valuable(const item& lhs, const item& rhs) noexcept {
return lhs.value > rhs.value || (lhs.value == rhs.value && lhs.count > rhs.count);
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
size_t amount_of_types = 0, capacity = 0;
std::cin >> capacity >> amount_of_types;
std::unordered_map<size_t, std::vector<item>> buckets;
buckets.reserve(amount_of_types);
for (size_t i = 0; i < amount_of_types; ++i) {
size_t weight = 0, value = 0, count = 0;
std::cin >> value >> weight >> count;
if (weight <= capacity) {
buckets[weight].push_back({value, count});
}
}
std::vector<size_t> dp(capacity + 1, 0);
for (auto& it : buckets) {
auto& bucket = it.second;
const size_t weight = it.first;
std::sort(bucket.begin(), bucket.end(), cmp_most_valuable);
size_t index = 0;
for (size_t count = 1; count * weight <= capacity && index < bucket.size(); ++count) {
for (size_t cap = capacity; cap >= weight; --cap) {
dp[cap] = std::max(dp[cap], dp[cap - weight] + bucket[index].value);
}
--bucket[index].count;
if (bucket[index].count == 0) {
++index;
}
}
}
std::cout << dp[capacity] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
2 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
2 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
3 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
0 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
2 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
3 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
0 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
27 ms |
3280 KB |
Output is correct |
36 |
Correct |
33 ms |
3280 KB |
Output is correct |
37 |
Correct |
31 ms |
3288 KB |
Output is correct |
38 |
Correct |
29 ms |
3064 KB |
Output is correct |
39 |
Correct |
34 ms |
2920 KB |
Output is correct |
40 |
Correct |
53 ms |
3564 KB |
Output is correct |
41 |
Correct |
38 ms |
3788 KB |
Output is correct |
42 |
Correct |
37 ms |
3668 KB |
Output is correct |
43 |
Correct |
46 ms |
3680 KB |
Output is correct |
44 |
Correct |
46 ms |
3668 KB |
Output is correct |
45 |
Correct |
32 ms |
3392 KB |
Output is correct |
46 |
Correct |
32 ms |
3328 KB |
Output is correct |
47 |
Correct |
35 ms |
3660 KB |
Output is correct |
48 |
Correct |
42 ms |
3520 KB |
Output is correct |
49 |
Correct |
29 ms |
3376 KB |
Output is correct |
50 |
Correct |
51 ms |
3100 KB |
Output is correct |