Submission #847801

#	Time	Username	Problem	Language	Result	Execution time	Memory
847801		suraj2411	Knapsack (NOI18_knapsack)	C++14	73 / 100	1024 ms	5980 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve(){
    ll s,n;
    cin >> s >> n;

    vector<pair<ll,ll>> dp(s+1,{-1,0});

    vector<vector<ll>> vec(n);
    for(int i = 0;i < n;i++){
        ll v,w,k;
        cin >> v >> w >> k;
        vec[i] = {v,w,k};
    }

    for(int i = 0;i <= s;i++){
        ll v = vec[0][0];
        ll w = vec[0][1];
        ll k = vec[0][2];
        if((i % w == 0) && ((i / w) <= k)){
            dp[i] = {v * (i / w),(i / w)};
        }
    }

    /*for(int i = 0;i <= s;i++){
        cout << "dp[0][" << i << "] = {" << dp[i].first << "," << dp[i].second << "}" << endl;
    }*/

    for(int i = 1;i < n;i++){
        vector<pair<ll,ll>> temp(s+1,{-1,0});
        ll v = vec[i][0];
        ll w = vec[i][1];
        ll k = vec[i][2];
        for(int j = 0;j <= s;j++){
            ll tot_val = -1;
            ll count = 0;

            if(dp[j].first != -1) tot_val = max(tot_val,dp[j].first);

            /*if((j - w >= 0) && (temp[j-w].first != -1) && (temp[j - w].second < k)){
                if(tot_val < (v + temp[j-w].first)){
                    tot_val = v + temp[j-w].first;
                    count = temp[j-w].second + 1;
                }
            }*/

            for(int p = 1;p <= k;p++){
                
                if(j - p*w < 0) break;

                if((j - p*w >= 0) && (dp[j - p*w].first != -1)){
                    if(tot_val < (dp[j - p*w].first + p*v)){
                        tot_val = dp[j - p*w].first + p*v;
                        count = p;
                    }
                }
            }
        
            temp[j] = {tot_val,count};

            //cout << "dp[" << i << "][" << j << "] = {" << temp[j].first << "," << temp[j].second << "}" << endl;
        }

        dp = temp;
    }

    ll answer = 0;
    for(int i = 1;i <= s;i++){
        answer = max(answer,dp[i].first);
    }

    cout << answer << endl;
}

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

    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

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