Submission #920547

#	Time	Username	Problem	Language	Result	Execution time	Memory
920547		AndrijaM	Knapsack (NOI18_knapsack)	C++14	0 / 100	1 ms	412 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

long long s,n;
vector<pair<long long,pair<long long,long long>>>x;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin>>s>>n;
    long long dp[s+1];
    long long D[s+1];
    memset(D,0,sizeof D);
    memset(dp,0,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}});
    }
    for(long long i=0;i<n;i++)
    {
        for(int idx=0;idx<s+1;idx++)
        {
            D[idx]=dp[idx];
        }
        for(long long j=1;j<=min(s,x[i].second.second);j++)
        {
            if(s-j*x[i].second.first<=0)break;
            for(long long p=s;p>=j*x[i].second.first;p--)
            {
                dp[p]=max(dp[p],D[p-j*x[i].second.first]+j*x[i].first);
            }
        }
    }
    cout<<dp[s]<<endl;
}

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