Submission #1161171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161171		summitclimbingdevil	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	16800 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;
    forn(i,n){
        ll v,w,k;
        cin>>v>>w>>k;
        ll c=1;
        while(k>=c && k>0){
            objs.push_back({v*c,c*w});
            k-=c;
            c=(c<<1);
        }
        if(k>0){
            objs.push_back({v*k,w*k});
        }
        
    }

    ll dp[s+1];
    // dp[0]=0;
    forn(i,s+1){
        dp[i]=0;
    }
    forn(j,objs.size()){
        auto [v,w]=objs[j];
        for(ll i=s-w;i>=0;i--){
            dp[i+w]=max(dp[i+w],dp[i]+v);
        }
    }

    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: 0 / 27