| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 970713 | 54skyxenon | Knapsack (NOI18_knapsack) | Cpython 3 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// https://oj.uz/problem/view/NOI18_knapsack
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int s, n;
cin >> s >> n;
vector<tuple<int, int, int>> items;
for (int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
items.push_back({v, w, k});
}
vector<vector<int>> dp(n + 1, vector<int>(s + 1));
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= s; j++) {
if (i == 0 || j == 0) {
continue;
}
auto [v, w, k] = items[i - 1];
for (int repeat = 1; repeat <= k && repeat * w <= j; repeat++) {
dp[i][j] = max(dp[i][j], v * repeat + dp[i - 1][j - repeat * w]);
}
}
}
cout << dp[n][s] << '\n';
}