Submission #1254332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254332		warrenn	Knapsack (NOI18_knapsack)	C++20	100 / 100	35 ms	3144 KiB

knapsack

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

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int s,n;
    cin>>s>>n;
    vector<pair<int,int> >wei[s+1];

    for(int q=1;q<=n;q++){
        int v,w,k;
        cin>>v>>w>>k;
        wei[w].push_back({v,k});
    }

    vector<pair<int,int> >hmm;
    for(int q=1;q<=s;q++){
        sort(wei[q].rbegin(),wei[q].rend());
        int idx=0;
        int rts=wei[q].size();
        for(int w=1;w<=s/q;w++){
            if(idx==rts)break;
            hmm.push_back({wei[q][idx].first,q});
            wei[q][idx].second--;
            if(wei[q][idx].second==0)idx++;
        }
    }
    int dp[s+1];
    for(int q=0;q<=s;q++)dp[q]=0;

    for(auto r : hmm){
        for(int wei=s;wei>=r.second;wei--){
            dp[wei]=max(dp[wei],dp[wei-r.second]+r.first);
        }
    }
    cout<<dp[s]<<endl;
}

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