#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
// Use long long for dp to avoid overflow.
vector<long long> dp(S + 1, 0);
for (int i = 0; i < N; i++){
long long v, w;
long long k;
cin >> v >> w >> k;
// Binary splitting: decompose the k copies into groups.
long long amount = 1;
while (k > 0) {
long long use = min(amount, k);
long long weight = w * use;
long long value = v * use;
// Process as a 0/1 knapsack item.
for (int j = S; j >= weight; j--) {
dp[j] = max(dp[j], dp[j - weight] + value);
}
k -= use;
amount *= 2;
}
}
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... |