Submission #1184857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184857		Godgift42	Knapsack (NOI18_knapsack)	C++20	0 / 100	1 ms	328 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)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<int,int>>());
        for(int l=0;l<=s;l++){
            dp[at][l]=dp[at-1][l];
            if(w<=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 << ans << "\n";
}

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