#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define endl '\n'
const int MOD = 1e9+7;
const int inf =1e9;
bool multi=false;
int main()
{
ll t=1;
if (multi) cin>>t;
while (t--) {
int s, n;
cin>>s>>n;
vector<pair<ll, ll>> items;
for (int i=0; i<n; i++) {
ll v,w,k;
cin>>v>>w>>k;
for (ll p=1; k>0; p<<=1) {
ll cnt = min(p, k);
items.push_back({v*cnt, w*cnt});
k-=cnt;
}
}
vector<ll> dp(s+1, 0);
for (auto item:items) {
ll val=item.first, weight=item.second;
for (int i=s; i>=weight; i--) {
dp[i]=max(dp[i], dp[i-weight]+val);
}
}
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... |