#include <bits/stdc++.h>
#define int long long
using namespace std;
int32_t main() {
int S, N;
cin >> S >> N;
vector<int>dp(S+1, 0);
vector<int>val(N);
vector<int>wt(N);
vector<int>k(N);
for(int i = 0; i<N; ++i)
{
cin >> val[i] >> wt[i] >> k[i];
}
for(int i = 0; i<N; ++i)
{
for(int p = 1; k[i]>0; p<<=1)
{
int power = min(p, k[i]);
int weight = power*wt[i];
int value = power*val[i];
for(int j = S; j>=weight; --j)
{
dp[j] = max(dp[j], dp[j-weight]+value);
}
k[i]-=power;
}
}
cout << dp[S];
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... |