#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ll n,k;
cin>>k>>n;
vector<ll> val(n),w(n),cap(n);
map<ll,vector<pair<ll,ll>>> mapa;
for(int i=0;i<n;i++)
{
cin>>val[i]>>w[i]>>cap[i];
mapa[w[i]].push_back({val[i],cap[i]});
}
vector<vector<ll>> dp(mapa.size()+1,vector<ll>(k+1,INT32_MIN));
dp[0][0]=0;
ll at=1;
for(auto &[a,v]:mapa)
{
sort(v.rbegin(),v.rend());
for(int i=0;i<=k;i++)
{
dp[at][i]=dp[at-1][i];
ll copies=0;
ll typeat=0;
ll profit=0;
ll curused=0;
while((copies+1)*a<=i&&typeat<=v.size())
{
copies++;
profit+=v[typeat].first;
if(dp[at-1][i-a*copies]!=INT32_MIN)
{
dp[at][i]=max(dp[at][i],dp[at-1][i-a*copies]+profit);
}
curused++;
if(curused==v[typeat].second)
{
curused=0;
typeat++;
}
}
}
at++;
}
cout<<*max_element(dp.back().begin(),dp.back().end())<<endl;
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... |