#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 998244353
#define ln '\n'
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int s{}, n{};
cin >> s >> n;
ll v{}, w{}, c{};
vector<ll> dp(s+1, 0);
for (int i = 0; i < n; ++i) {
cin >> v >> w >> c;
ll maxItems = s / w;
if (c > maxItems) c = maxItems;
for (ll k = 1; c > 0; k *= 2) {
ll amount = min(k, c);
ll totalWeight = w * amount;
for (int j = s; j >= totalWeight; j--) {
dp[j] = max(dp[j], dp[j - totalWeight] + v * amount);
}
c -= amount;
}
}
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... |