#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll MOD = 1e9 +7;
int MAX_C = 1e8+1;
int main(){
int s,n;
cin >> s >> n;
vector <int> w(n);
vector <ll> v(n);
vector <ll> k(n);
for(int i = 0 ; i < n ;i++){
cin >> v[i] >> w[i] >> k[i];
}
vector <ll> dp(s+1,0);
for(int i = 0 ; i < n ; i++){
for(int j = s; j >= w[i] ; j--){
int u = j/w[i];
if(k[i] < u){
u = k[i];
}
for(int a = 1; a <= u ;a++){
dp[j] = max(dp[j],dp[j - a*w[i]] + a*v[i]);
}
}
}
cout << dp[s] << 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... |