#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int s, n;
cin >> s >> n;
vector<pair<int, int>> items;
// Binary Decomposition of bounded items
for (int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
if (w <= 0 || k <= 0) continue; // Skip invalid items
for (int p = 1; k > 0; p <<= 1) {
int cnt = min(p, k);
items.emplace_back(v * cnt, w * cnt);
k -= cnt;
}
}
// Standard 0/1 Knapsack
vector<int> dp(s + 1, 0);
for (auto &[val, wt] : items) {
if (wt > s) continue; // Skip items that are too heavy
for (int j = s; j >= wt; --j) {
dp[j] = max(dp[j], dp[j - wt] + val);
}
}
cout << dp[s] << "\n";
return 0;
}
# | 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... |