제출 #847784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
847784		suraj2411	Knapsack (NOI18_knapsack)	C++14	12 / 100	1 ms	348 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;
                }
            }

            

            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: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27