Submission #1298688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298688		xoikhuc	Knapsack (NOI18_knapsack)	C++20	37 / 100	1095 ms	2768 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long
int s,n;

struct item{
    int v,w,k;
    item():v(0),w(0),k(0) {}
    item(int V,int W,int K):v(V),w(W),k(K) {}
};

vector<item> items(100001);
int dp[2001];
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>s>>n; 
    for(int i=1;i<=n;i++){
        int v,w,k;
        cin>>v>>w>>k;
        items[i]=item(v,w,k);
    }

    for(int i=1;i<=n;i++){
        int v=items[i].v, w=items[i].w, k=items[i].k;

        for(int j=2000;j>=w;j--){ //weight
            for(int p=1;p<=k;p++){ //number of copies
                if(j-p*w==0) dp[p*w]=max(dp[p*w],p*v);
                else if(j-p*w>0) dp[j]=max(dp[j],dp[j-p*w]+p*v);
            }
            
        }

    }

    cout<<dp[s];
}

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