#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
int N, S; cin >> S >> N;
vector<long long> vfw(S+1, 0);
vector<long long> aus(S+1);
auto upd = [&](int v, int w) {
for (int i = S; i >= w; i--) {
aus[i] = max(vfw[i], vfw[i-w]+v);
}
};
for (int i = 0; i < N; i++) {
int V, W, K; cin >> V >> W >> K;
fill(aus.begin(), aus.end(), 0);
for (int k = 1; k <= K; k<<=1) {
upd(V*k, W*k);
K-=k;
vfw = aus;
}
if (K > 0) upd(V*K, W*K);
vfw = aus;
}
long long best = 0;
for (int i = 0; i <= S; i++) {
best = max(best, vfw[i]);
}
cout << best;
}
# | 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... |