제출 #1256105

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256105		rajinnyo	Knapsack (NOI18_knapsack)	C++20	100 / 100	50 ms	1628 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
// JANGAN LUPA CEK PERLU LL NGGAK
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define miku ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int lim=2000;
int prefval[lim+1][lim+1];
vector<pii>w[lim+1];
int dp[lim+10];
signed main(){
    miku
    int s,n;cin>>s>>n;
    for(int i=1;i<=n;i++){
        int v,ww,k;cin>>v>>ww>>k;
        w[ww].pb({v,k});
    }
    for(int i=1;i<=lim;i++)sort(w[i].begin(),w[i].end(),greater<pii>());
    for(int j=1;j<=lim;j++){
        //kita coba knapsack untuk tiap weigth
        // kita cuman bisa pake segini kali
        if(!w[j].size())continue;
        for(int i=s;i>=1;i--){
            int v=0,cnt=0,nw=0,las=0;
            for(int k=1;k<=lim/j;k++){
                if(w[j][nw].se<cnt+1){
                    if(nw+1<w[j].size()){
                        nw++;
                        cnt=0;
                    }
                    else break; 
                }
                las+=w[j][nw].fi;
                cnt++;
                if(i-j*k<0) break;
                dp[i]=max(dp[i],dp[i-j*k]+las);
            }
        }
        // cout<<j<<endl;

    }
    cout<<dp[s];
}

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