#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int smax = 2000;
ll dp[2][smax+5];
int main (){
ios::sync_with_stdio(0);
cin.tie(0);
int s,n;
cin >> s >> n;
int cur = 0, nxt = 1;
for(int i=1;i<=n;i++){
ll v,w,k;
cin >> v >> w >> k;
ll pw = 1;
while(k > 0){
ll take = min(pw, k);
k -= take;
int wt = (int)(w * take);
ll val = v * take;
for(int cap=0; cap<=s; cap++) dp[nxt][cap] = dp[cur][cap];
for(int cap=wt; cap<=s; cap++){
dp[nxt][cap] = max(dp[nxt][cap], dp[cur][cap-wt] + val);
}
swap(cur,nxt);
pw <<= 1;
}
}
cout << dp[cur][s] << "\n";
}
# | 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... |