# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1236531 | mirbek01 | Knapsack (NOI18_knapsack) | C++20 | 75 ms | 1656 KiB |
#include <bits/stdc++.h>
using namespace std;
int n, s;
int main() {
cin >> s >> n;
vector < vector <pair <int, int>> > vc(s + 1);
for (int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
vc[w].push_back({v, k});
}
vector < vector <int> > vec(s + 1);
for (int i = 1; i <= s; i++) {
sort(vc[i].rbegin(), vc[i].rend());
int kol = s / i;
for (auto [val, cnt] : vc[i]) {
int mn = min(kol, cnt);
for (int j = 0; j < mn; j++) {
vec[i].push_back(val);
}
kol -= mn;
}
}
vector <int> dp(s + 1, -1e18);
dp[0] = 0;
for (int w = 1; w <= s; w++) {
for (int x : vec[w]) {
for (int W = s; W >= w; W--) {
dp[W] = max(dp[W], dp[W - w] + x);
}
}
}
int ans = 0;
for (int i = 1; i <= s; i++) ans = max(ans, dp[i]);
cout << ans << endl;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |