#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
ll solve(vector<int> v, vector<int> w, vector<int> k, int S, int n) {
vector<int> vv, ww;
for (int i = 1; i <= n; ++i) {
int value = v[i], weight = w[i], count = k[i];
for (int b = 1; count > 0; b *= 2) {
int take = min(b, count);
vv.push_back(value * take);
ww.push_back(weight * take);
count -= take;
}
}
vector<ll> dp(S + 1, 0);
for (int i = 0; i < vv.size(); ++i) {
for (int j = S; j >= ww[i]; --j) {
dp[j] = max(dp[j], dp[j - ww[i]] + vv[i]);
}
}
return dp[S];
}
int main() {
int S, N;
cin >> S >> N;
vector<int> v(N + 1), w(N + 1), k(N + 1);
for (int i = 1; i <= N; ++i) {
cin >> v[i] >> w[i] >> k[i];
}
cout << solve(v, w, k, S, N) << 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... |