제출 #1219585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219585		sam230609	Knapsack (NOI18_knapsack)	C++20	100 / 100	84 ms	5188 KiB

knapsack

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
ll s,n,v[100001],w[100001],k[100001],maxV=0,f[2001];
vector<pair<ll,ll>> a[2001];
int main(){
    cin >>s>>n;
    for(ll i=1;i<=n;i++) cin >>v[i]>>w[i]>>k[i],maxV=max(maxV,k[i]);
    memset(f,0,sizeof(f));
    for(ll i=1;i<=n;i++) a[w[i]].push_back({v[i],k[i]});
    for(ll i=0;i<=s;i++){
        if(a[i].size()==0) continue; ll pos=0;
        sort(a[i].begin(),a[i].end(),greater<pair<ll,ll>>());
        for(ll j=0;j*i<s;j++){
            if(pos>=a[i].size()) break;
            for(ll k=s;k>=i;k--) f[k]=max(f[k],f[k-i]+a[i][pos].fi);
            a[i][pos].se--; if(a[i][pos].se==0) pos++;
        }
    }cout <<f[s];
}

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