Submission #807179

#	Time	Username	Problem	Language	Result	Execution time	Memory
807179		sirigith	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	340 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;


int main(){
    long long s,n; cin>>s>>n;
    vector<vector<long long>> items(n);
    for (long long i=0;i<n;i++){
        long long x,y,z; cin>>x>>y>>z;
        items[i]={x,y,z};
    }
    vector<long long> dp(2*s,-1);
    dp[0]=0;
    for (auto j: items){
        vector<long long> cnt(s+1,j[2]); //num remaining of this particular item, take max
        for (long long i=0; i<s; i++){
            if ((i+j[1]<=s) and (dp[i]!=-1) and (cnt[i]>0)){
                if ((dp[i+j[1]]==-1) or (dp[i+j[1]]<(dp[i]+j[0]))){
                    dp[i+j[1]]=dp[i]+j[0];
                    cnt[i+j[1]]=cnt[i]-1;
                } else if (dp[i+j[1]]==dp[i]+j[0]){
                    cnt[i+j[1]]=max(cnt[i+j[1]],cnt[i]-1);
                }
            }
        }
    }
    long long ans=0;
    for (auto i: dp){
        ans=max(ans,i);
    }
    cout<<ans<<'\n';
}

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