Submission #1258189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258189		abcd1234	Knapsack (NOI18_knapsack)	C++20	100 / 100	110 ms	5048 KiB

knapsack

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
using ll = long long;

vector<vector<ll>> process(vector<vector<pair<ll, ll>>> items, int s){
    vector<vector<ll>> res(2001);
    for(int i = 1; i <= 2000; i++){
        int allowed = s / i;
        vector<pair<ll, ll>> temp = items[i];
        sort(temp.begin(), temp.end());
        reverse(temp.begin(), temp.end());
        if(!temp.empty()){
            int idx = 0;
            while(idx < temp.size() && allowed > 0){
                ll curr = temp[idx].second;
                ll value = temp[idx].first;
                if(allowed >= curr){
                    allowed -= curr;
                    while(curr--) res[i].push_back(value);
                }
                else{
                    while(allowed--) res[i].push_back(value);
                }
                idx++;
            }
        }
    }
    return res;
}

int main()
{
    int s, n; cin >> s >> n;
    //store {v_i, k_i} in weight_i
    vector<vector<pair<ll, ll>>> items(2001);
    for(int i = 0; i < n; i++){
        ll v, w, k; cin >> v >> w >> k;
        items[w].push_back({v, k});
    }
    auto res = process(items, s);

    vector<ll> dp(2001, 0);
    for(int w = 1; w <= s; w++){
        for(int val : res[w]){
            for(int i = s; i >= w; i--){
                dp[i] = max(dp[i], dp[i - w] + val);
            }
        }
    }
    cout << dp[s] << endl;
}

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