Submission #1127231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127231		epictrolltoast	Knapsack (NOI18_knapsack)	C++17	73 / 100	587 ms	327680 KiB

knapsack

#include <bits/stdc++.h>
#define vec vector
#define pp pair<int, vector<int>>
using namespace std;


int32_t main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int s, n;
    cin >> s >> n;

    vec<int> prices, weight, number;
    for(int i = 0; i < n; i++){
        int p ,w ,n;
        cin >> p >> w >> n;
        prices.push_back(p);
        weight.push_back(w);
        number.push_back(n);
    }

    vec<pair<int, vec<int>>> storage; //Value, list of items
    storage.reserve(s + 10);
    for (int i = 0; i <= s; i++)
    {
        vec<int> buffs;
        buffs.reserve(n);
        storage.push_back(make_pair(0, buffs));
    }

    vec<int> toAdd;
    for(int i = 0; i < n; i++){
        
        toAdd.push_back(0);
    }
    storage[0].second = toAdd;

    for(int i = 0; i < s; i++){
        if(storage[i].second.size() != 0 || storage[i].first > 0){
            for(int j = 0; j < n; j++){
                if(storage[i].second[j] < number[j]){
                    int target = i + weight[j];
                    if(target <= s){
                        int value = storage[i].first + prices[j];
                        if(value > storage[target].first){
                            storage[target].first = value;
                            storage[target].second = storage[i].second;
                            storage[target].second[j]++;
                        }
                    }
                }
            }
        }
    }

    int max = 0;
    for(int i = 0; i <= s; i++){
        if(max < storage[i].first)
            max = storage[i].first;
    }
 
    cout << max << endl;

    return 0;
}

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