Submission #920533

#	Time	Username	Problem	Language	Result	Execution time	Memory
920533		AndrijaM	Knapsack (NOI18_knapsack)	C++14	0 / 100	1 ms	348 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(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}});
    }
    long long ans=0;
    for(long long i=0;i<n;i++)
    {
        for(int idx=0;idx<s+1;idx++)
        {
            D[idx]=dp[idx];
        }
        for(long long j=min(s,x[i].second.second);j>=1;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(max(D[p],dp[p]),D[p-j*x[i].second.first]+j*x[i].first);
            }
            ///cout<<i<<" "<<j<<" "<<dp[20]<<endl;
        }
    }
    cout<<dp[s]<<endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:21:15: warning: unused variable 'ans' [-Wunused-variable]
   21 |     long long ans=0;
      |               ^~~

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