Submission #1196268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196268		a0ms1n	Knapsack (NOI18_knapsack)	C++20	17 / 100	2 ms	328 KiB

knapsack

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

int n;

// W -> V

// Weight i can have S/i items (Greedy by choose most value first (remove min value if exceeds))
// = S + S/2 + S/3 + ... S/S -> Sln(S);     
priority_queue<int,vector<int>,greater<int>> prod[2020]; 
int dp[(int)2001]={0};   

vector<pair<int,int>> V;

/*

dp[n][w] = max(dp[n-1][w],dp[n-1][w-W]+V)

*/



signed main(){
    int s,n;cin>>s>>n;
    for(int i=0;i<n;i++){
        int V,W,K;cin>>V>>W>>K;
        for(int w=W,k=1;k<=K && w<=s;k++,w+=W){
            //cout<<w<<' '<<V*k<<'\n';
            prod[w].push(V*k);
            if(prod[w].size() > s/w + 20)prod[w].pop();
        }
    }
    for(int i=0;i<=s;i++){
        while(prod[i].size())V.push_back({i,prod[i].top()}),prod[i].pop();
    }
    n = V.size();
    for(int i=0;i<n;i++){
        //cout<<V[i].first<<' '<<V[i].second<<'\n';
        for(int j=s;j>=V[i].first;j--){
            dp[j] = max(dp[j],dp[j-V[i].first]+V[i].second);
        }
    }
    cout<<dp[s];
    return 0;
}

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