#include <bits/stdc++.h>
using namespace std;
int main() {
int s,n;
cin >> s >> n;
vector<int> weights(n);
vector<int> values(n);
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> values[i] >> weights[i] >> nums[i];
}
vector<vector<int> > dp(n+1,vector<int>(s+1,0));
for (int i = 0; i <= s; i++) {
dp[0][i]=0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= s; j++) {
dp[i][j]=dp[i-1][j];
for (int k = 1; k <= nums[n-i]; k++) {
if (j>=weights[n-i]*k) {
dp[i][j]=max(dp[i][j],dp[i-1][j-weights[n-i]*k]+values[n-i]*k);
} else {
break;
}
}
}
}
cout << dp[n][s];
}
# | 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... |