Submission #501359

#	Time	Username	Problem	Language	Result	Execution time	Memory
501359		ala2	Knapsack (NOI18_knapsack)	C++14	49 / 100	45 ms	81160 KiB

knapsack

/*
ID: alaa523
LANG: C++11
PROB: Fruit Feast
*/
#include <bits/stdc++.h>

#define pb push_back
#define int long long
#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 dp[1005][10005];
int f(int i,int sum)
{   if(sum>s)
        return -1e17;
    if(i==a.size())
        return 0;
    if(dp[i][sum]!=-1)
        return dp[i][sum];
    return dp[i][sum]=max(f(i+1,sum+a[i].S)+a[i].F,f(i+1,sum));
}
signed main()
{
    memset(dp,-1,sizeof dp);
 	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;

}

Compilation message (stderr)

knapsack.cpp: In function 'long long int f(long long int, long long int)':
knapsack.cpp:22:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     if(i==a.size())
      |        ~^~~~~~~~~~

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