Submission #1184870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184870		Godgift42	Knapsack (NOI18_knapsack)	C++20	100 / 100	100 ms	34404 KiB

knapsack

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

using ll = long long;

int main(){
    int n,s;
    cin >> s >> n;
    map<int,vector<pair<ll,int>>> bw;
    for(int i=0;i<n;i++){
        ll v;
        int w,k;
        cin >> v >> w >> k;
        if(w<=s and k>0)bw[w].push_back({v,k});
    }
    vector<vector<ll>> dp(bw.size()+1,vector<ll>(s+1,-1));
    dp[0][0]=0;
    int at=0;
    ll ans=0;
    for(auto &[w,items]:bw){
        at++;
        sort(items.begin(),items.end(),greater<pair<ll,int>>());
        for(int l=0;l<=s;l++){
            dp[at][l]=dp[at-1][l];
            int cr=0;
            int id=0;
            int cur=0;
            ll pr=0;
            while(id<items.size() and (cr+1)*w<=l){
                cr++;
                cur++;
                pr+=items[id].first;
                if(dp[at-1][l-cr*w]!=-1)dp[at][l]=max(dp[at][l],dp[at-1][l-cr*w]+pr);
                if(cur==items[id].second){
                    cur=0;
                    id++;
                }
            }
            ans=max(ans,dp[at][l]);
        }
    }
    cout << *max_element(dp.back().begin(), dp.back().end()) << endl;
}

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