Submission #501358

#	Time	Username	Problem	Language	Result	Execution time	Memory
501358		ala2	Knapsack (NOI18_knapsack)	C++14	0 / 100	0 ms	332 KiB

knapsack

/*
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)<<endl;

}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27