Submission #1287780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287780		eri16	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	2612 KiB

knapsack

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

void subtask_1(int wmax,int n, vector<int> v, vector <int> w, vector <int> k){cout<<min(k[0],wmax/w[0])*v[0];}

void subtask_2(int wmax,int n, vector<int> v, vector <int> w, vector <int> tt){
    
    int dp[wmax+1];
    
    for (int i=0; i<=wmax; i++){dp[i]=-1;}
    
    dp[0]=0;
    
    for (int i=0; i<n; i++){
        for (int j=wmax; j>=0; j--){
            
            if (dp[j]!=-1){
                int t=1;
                for (int k=j+w[i]; t<=tt[i] && k<=wmax; k+=w[i]){
                    dp[k]=max(dp[k],dp[j]+t*v[i]); 
                    t++;
                }
            }
        }
    }
    
    int mx=0;
    
    for (int i=0; i<=wmax; i++){
        mx=max(mx,dp[i]);
    }
    
    cout<<mx;
    
}





int main(){
    
    int wmax,n;
    
    cin>>wmax>>n;
    
    vector <int> V(n),W(n),K(n);
    
    for (int i=0; i<n; i++){
        cin>>V[i]>>W[i]>>K[i];
    }
    
    if (n==1)subtask_1(wmax,n,V,W,K);
    
    else{subtask_2(wmax,n,V,W,K);}
    
}

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