This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
ID: alaa523
LANG: C++11
PROB: Fruit Feast
*/
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define F first
#define S second
using namespace std;
int n,s;
int v[1001000];
int w[1001000];
int k[1000100];
vector<pair<int,int>>a;
int f(int i,int sum)
{
if(i==n)
return 0;
if(sum>s)
return -1e17;
return max(f(i+1,sum+a[i].S)+a[i].F,f(i+1,sum));
}
signed main()
{
cin>>s>>n;
for(int i=0;i<n;i++)
{
cin>>v[i]>>w[i]>>k[i];
k[i]=min(k[i],s);
}
for(int i=0;i<n;i++)
{
for(int j=0;j<k[i];j++)
{
a.pb({v[i],w[i]});
}
}
cout<<f(0,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... |