Submission #919244

#	Time	Username	Problem	Language	Result	Execution time	Memory
919244		AndrijaM	Knapsack (NOI18_knapsack)	C++14	73 / 100	286 ms	6860 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

long long s,n;
vector<pair<long long,pair<long long,long long>>>x;
long long dp[105][2005];

long long f(long long idx,long long sum)
{
    if(idx==n)
    {
        return 0;
    }
    if(dp[idx][sum]!=-1)
    {
        return dp[idx][sum];
    }
    long long rez=0;
    rez=max(rez, f(idx+1,sum));
    for(long long i=1;i<=min(s,x[idx].second.second);i++)
    {
        if(i*x[idx].second.first+sum>s)
        {
            break;
        }
        rez=max(rez, f(idx+1,i*x[idx].second.first+sum)+x[idx].first*i);
    }
    return dp[idx][sum]=rez;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin>>s>>n;
    memset(dp,-1,sizeof dp);
    for(long long i=0;i<n;i++)
    {
        long long v,w,k;
        cin>>v>>w>>k;
        x.push_back({v,{w,k}});
    }
    cout<<f(0,0)<<endl;
}

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