제출 #1158878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158878		ulvix	Knapsack (NOI18_knapsack)	C++20	100 / 100	71 ms	3088 KiB

knapsack

#include<bits/stdc++.h>
#define ll long long
#define all(x) x.begin(),x.end()
using namespace std;
vector<pair<ll,ll>> wei[2005];
ll dp[2005];
int main(){
    ll s,n,ans=0;
    cin>>s>>n;
    for(ll i=0;i<n;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        wei[b].push_back({a,c});
    }
    for(ll i=1;i<=s;i++){
        sort(wei[i].rbegin(),wei[i].rend());
        ll idx=0;
        for(ll j=0;j<s/i;j++){
            if(idx>=wei[i].size()) break;
            for(ll k=s;k>=i;k--){
                dp[k]=max(dp[k],dp[k-i]+wei[i][idx].first);
                ans=max(ans,dp[k]);
            }
        wei[i][idx].second--;
        if(wei[i][idx].second==0) idx++;
        }
    }
    cout<<dp[s];
}

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