| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1319309 | aslayeryl81 | Knapsack (NOI18_knapsack) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int s, n;
cin >> s >> n;
vector<int> dp(s + 1, 0);
for(int i = 0; i < n; i++)
{
int v, w, k;
cin >> v >> w >> k;
int maxx = min((s / w), k);
for(int p = 1; maxx > 0; p <<= 1)
{
int dem = min(p, maxx);
maxx -= dem;
int W = dem * W;
int val = dem * V;
for(int w = s; w >= W; w--)
dp[w] = max(dp[w], dp[w - W] + val);
}
}
cout << *max_element(dp.begin(), dp.end());
return 0;
}
