Submission #975171

#	Time	Username	Problem	Language	Result	Execution time	Memory
975171		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	681 ms	159816 KiB

knapsack

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

const int maks=2000;
const int maxitem=20000;
const int inf=2e9;
int s,n;
vector<pair<int,int> > weight[maks+5];
vector<pair<int,int> > item;
int dp[maxitem+5][maks+5];

int cek(int idx,int brt){
    if(brt<0)return -inf;
    if(idx==(long long)item.size())return 0;
    int &res=dp[idx][brt];
    if(res!=-1)return res;
    auto[w,v]=item[idx];
    return res=max(cek(idx+1,brt),cek(idx+1,brt-w)+v);
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>s>>n;
    for(int r=0;r<n;r++){
        int v,w,k;
        cin>>v>>w>>k;
        weight[w].push_back({v,k});
    }
    for(int d=1;d<=maks;d++){
        sort(weight[d].begin(),weight[d].end());
        int ambil= maks/d +1;
        while(ambil!=0 && !weight[d].empty()){
            auto &[v, k] = weight[d].back();
            item.push_back({d, v});
            k--;
            ambil--;
            if (k == 0) weight[d].pop_back();
        }
    }
    memset(dp,-1,sizeof dp);
    cout<<cek(0,s);
}

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