| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 788955 | codergirl | Knapsack (NOI18_knapsack) | C++14 | 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.
#include <iostream>
#include <cmath>
int main() {
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
long v[1000000], w[1000000]; int s, n; std::cin >> s >> n;
long counter = 0, t; int x, y, z;
for (int i=0; i < n; i++) {
std::cin >> y >> z >> x;
for (int j=0; j < 30; j++) {
if (x == 0) break;
t = std::pow(2, j);
if (x < t) {
if (z*x > s) break;
v[counter] = y*x, w[counter++] = z*x; break;
} else {
if (z*t > s) break;
v[counter] = y*t, w[counter++] = z*t; x -= t;
}
}
}
long arr[2][s+1]{};
//for (long j=0; j <= s; j++) arr[0][j] = 0;
//arr[1][0] = 0;
int a=0, b=1;
for (long i=1; i <= counter; i++) {
a = 1-a, b = 1-b;
for (long j=1; j <= s; j++) {
if (j-w[i-1] >= 0) arr[a][j] = std::max(arr[b][j-w[i-1]]+v[i-1], arr[b][j]);
else arr[a][j] = arr[b][j];
}
}
std::cout << arr[a][s] << '\n';
}