#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, s;
cin >> s >> n;
vector<ll> v(n), w(n), k(n);
for (int i = 0; i < n; ++i){
cin >> v[i] >> w[i] >> k[i];
}
vector<ll> dp(s + 1);
for (int i = 0; i < n; ++i){
vector<ll> temp(s + 1);
for (int j = 0; j <= s; ++j){
if (j == 0 || dp[j] > 0){
if (j + w[i] <= s && dp[j + w[i]] < dp[j] + v[i] && temp[j] < k[i]){
temp[j + w[i]] += temp[j] + 1;
dp[j + w[i]] = dp[j] + v[i];
}
}
}
}
ll ans = 0;
for (int i = 1; i <= s; ++i) ans = max(ans, dp[i]);
cout << ans << '\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... |