#include <bits/stdc++.h>
#define int long long
using namespace std;
int32_t main() {
int S, N;
cin >> S >> N;
vector<pair<int, int>> final_items;
for(int i = 0; i < N; ++i) {
int val, wt, k;
cin >> val >> wt >> k;
for(int b = 1; k > 0; b <<= 1) {
int cnt = min(b, k);
k -= cnt;
final_items.push_back({wt * cnt, val * cnt});
}
}
vector<int> dp(S + 1, 0);
for(auto& [w, v] : final_items) {
for(int j = S; j >= w; --j) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
cout << dp[S];
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... |