#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ll S, N;
cin >> S >> N;
vector<ll> dp(S + 1, 0); // Start with 0, no items taken
for (int i = 0; i < N; i++) {
ll v, w, k;
cin >> v >> w >> k;
// ✅ Treat as unbounded knapsack if weight × k exceeds capacity
if (w * k >= S) {
for (ll j = w; j <= S; j++) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
else {
// Binary optimization for bounded knapsack
for (ll cnt = 1; k > 0; cnt <<= 1) {
ll take = min(cnt, k);
k -= take;
ll totalValue = v * take;
ll totalWeight = w * take;
for (ll j = S; j >= totalWeight; j--) {
dp[j] = max(dp[j], dp[j - totalWeight] + totalValue);
}
}
}
}
cout << *max_element(dp.begin(), dp.end()) << endl;
}
# | 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... |