Submission #1287923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287923		eri16	Knapsack (NOI18_knapsack)	C++20	100 / 100	112 ms	20052 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;
    
}

void subtask_3(int wmax,int n, vector<int> v, vector <int> w, vector <int> tt){
    vector <pair<int,pair<int,int>>> baraa;
    
    for (int i=0; i<n; i++){
        baraa.push_back({w[i],{v[i],tt[i]}});
    }
    
    sort(baraa.begin(),baraa.end(),[](auto &a, auto &b){
    
        if (a.first==b.first){
            return b.second.first<a.second.first;
        }
        return a.first<b.first;
        
    });
    
    vector <int> bst[2001];
    
    for (int i=0; i<n; i++){
        if (baraa[i].first<2001){
            for (int j=0; j<baraa[i].second.second && bst[baraa[i].first].size()<2001; j++){
                bst[baraa[i].first].push_back(baraa[i].second.first);
            }
        }
    }
    
    int dp[wmax+1];
    
    for (int i=0; i<=wmax; i++){dp[i]=-1;}
    
    dp[0]=0;
    
    for (int i=1; i<2001; i++){
        for (int j=wmax; j>=0; j--){
            
            if (dp[j]!=-1){
                int sm=0;
                int t4=0;
                for (int k=j+i; k<=wmax && t4<bst[i].size(); k+=i){
                    dp[k]=max(dp[k],dp[j]+sm+bst[i][t4]); 
                    sm+=bst[i][t4];                    
                    t4++;
                }
            }
        }
    }
    
    int mx=0;
    
    for (int i=0; i<=wmax; i++){
        mx=max(mx,dp[i]);
    }
    
    cout<<mx;    
    
    
    
    
}
/*

2000 6
5000 15 1005
100 1 2005
100 10 2005
50 1 2005
1 10 20
100 100 1


*/

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 if(n<=100){subtask_2(wmax,n,V,W,K);}
    else{subtask_3(wmax,n,V,W,K);}
}

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