#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e4+1;
vector <pair <int,int> > vec[2001];
signed main()
{
int s,n;
cin>>s>>n;
vector <int> v(n+1);
vector <int> w(n+1);
vector <int> k(n+1);
vector <int> c;
vector <int> h;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i]>>k[i];
vec[w[i]].push_back({v[i],k[i]});
}
for(int i=1;i<=s;i++)
{
sort(vec[i].rbegin(),vec[i].rend());
int cnt=s/i;
for(auto [vi,ka] : vec[i])
{
for(int j=0;j<min(ka,cnt);j++)
{
c.push_back(vi);
h.push_back(i);
}
cnt-=ka;
}
}
vector <int> dp(s+1);
for(int i=0;i<h.size();i++)
{
for(int j=s;j>=h[i];j--)
{
dp[j]=max(dp[j],dp[j-h[i]]+c[i]);
}
}
cout<<dp[s];
}
# | 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... |