#include <bits/stdc++.h>
using namespace std;
struct Item {
long long v, w; // use long long to avoid overflow
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
vector<Item> items;
items.reserve(N * 30); // prevent realloc overhead
for (int i = 0; i < N; i++) {
long long V, W, K;
cin >> V >> W >> K;
for (long long p = 1; K > 0; p <<= 1) {
long long cnt = min(p, K);
items.push_back({V * cnt, W * cnt});
K -= cnt;
}
}
vector<long long> dp(S + 1, 0);
for (auto &it : items) {
for (int j = S; j >= it.w; j--) {
dp[j] = max(dp[j], dp[j - it.w] + it.v);
}
}
cout << dp[S] << "\n";
}
# | 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... |