제출 #1161183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161183		summitclimbingdevil	Knapsack (NOI18_knapsack)	C++20	100 / 100	49 ms	8684 KiB

knapsack

#include<bits/stdc++.h>

using ll = long long;
using ld = long double;
using namespace std;
#define endl "\n";
#define ff first
#define ss second

#define forn(i,n) for(int i=0;i<n;i++)
#define dbgv(v) cout<<#v<<" "<<v<<endl
#define dbga(a,n) forn(i,n-1) {cout<<a[i]<<' ';} cout<<a[n-1]<<'\n';
void solve(){
    ll s,n;
    cin>>s>>n;
    // vector<pair<ll,ll>> objs;
    vector<priority_queue<ll>> objs(s);
    forn(i,n){
        ll v,w,k;
        cin>>v>>w>>k;
        ll c=1;
        while(k>=c && k>0 && c>0 && c*w<=s){
            // objs.push_back({v*c,c*w});
            objs[c*w-1].push(v*c);
            k-=c;
            c=(c<<1);
        }
        if(k>0 && w*k<=s){
            objs[w*k-1].push(v*k);
        }
        
    }

    ll dp[s+1];
    // dp[0]=0;
    forn(i,s+1){
        dp[i]=0;
    }
    forn(j,objs.size()){
        // auto [v,w]=objs[j];
        ll si=objs[j].size();
        for(int k=0;k<min(s/(j+1)+1,si);k++){
            ll v=objs[j].top();
            objs[j].pop();
            ll w=j+1;
            for(ll i=s-w;i>=0;i--){
                dp[i+w]=max(dp[i+w],dp[i]+v);
            }
        }
        // if(w>s)continue;
        
    }

    cout<<dp[s]<<endl;

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    // cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

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