# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
629189 | huyle | Knapsack (NOI18_knapsack) | C++17 | 366 ms | 262144 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.
#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) 69
#endif
const i64 inf = 1e18;
int32_t main() {
int s, n;
scanf("%d %d", &s, &n);
std::vector<int> v(n), w(n), k(n);
for (int i = 0; i < n; ++i) {
scanf("%d %d %d", &v[i], &w[i], &k[i]);
}
std::vector<std::vector<i64>> dp(n + 1, std::vector<i64>(s + 1, -inf));
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int d = 0; d <= k[i]; ++d) {
i64 tmp = (i64)d * w[i];
if (tmp > s)
break;
for (int j = (int)tmp; j <= s; ++j) {
if (dp[i][j - tmp] == -inf)
continue;
dp[i + 1][j] = std::max(dp[i + 1][j], dp[i][j - tmp] + (i64)d * v[i]);
}
}
}
printf("%lld\n", *std::max_element(dp[n].begin(), dp[n].end()));
}
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... |