Submission #975437

#	Time	Username	Problem	Language	Result	Execution time	Memory
975437		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	690 ms	161864 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 -1e10;
    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()){
            pair<int,int>&e = weight[d].back();
            item.push_back({d, e.first});
            e.second--;
            ambil--;
            if (e.second == 0) weight[d].pop_back();
        }
    }
    memset(dp,-1,sizeof dp);
    cout<<cek(0,s);
}

Compilation message (stderr)

knapsack.cpp: In function 'int cek(int, int)':
knapsack.cpp:13:22: warning: overflow in conversion from 'double' to 'int' changes value from '-1.0e+10' to '-2147483648' [-Woverflow]
   13 |     if(brt<0)return -1e10;
      |                      ^~~~

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