Submission #701176

#	Time	Username	Problem	Language	Result	Execution time	Memory
701176		KidOfCubes	Knapsack (NOI18_knapsack)	C++17	37 / 100	1083 ms	336 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

struct item {
    int value;
    int weight;
    int amount;
};

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

    int S,N;
    cin >> S >> N;
    vector<item> itemTypes(N+1,item());
    int totalItems=0;
    for(int i=0;i<N;i++){
        cin >> itemTypes[i].value >> itemTypes[i].weight >> itemTypes[i].amount;
        totalItems+=itemTypes[i].amount;
    }

    vector<int> dp(S+1,0); //max value for [i(this weight)][j(how many used)]
    vector<int> dpAfter(S+1,0); //max value for [i(this weight)][j(how many used)]

    int currentItemIndex = 0;
    item currentItem = itemTypes[currentItemIndex];
    int count=0;
    int maxValue=0;
    // cout << "GO\n";

    for(int item=0;item<totalItems;item++){
        // cout << "dping on "<<currentItemIndex<<endl;
        for(int i=0;i<S;i++){
            // dp[i]=max(dp[i],dp[i]);
            if(i+currentItem.weight<=S){
                // cout << "i"<<i<<"+weight("<<currentItem.weight<<") <= "<<S<<endl;
                dpAfter[i+currentItem.weight]=max(dpAfter[i+currentItem.weight],dp[i]+currentItem.value);
                maxValue=max(maxValue,dpAfter[i+currentItem.weight]);
            }
            // cout << "i is now "<<i<<endl;
        }
        for(int i=0;i<S+1;i++){
            dp[i]=dpAfter[i];
        }
        // fill(dpAfter.begin(),dpAfter.end(),0);
        count++;
        if(count==currentItem.amount){
            count=0;
            currentItemIndex++;
            currentItem = itemTypes[currentItemIndex];
        }
    }
    cout << maxValue << "\n";


}

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