Submission #1345426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1345426		aaryyann	Knapsack (NOI18_knapsack)	C++20	0 / 100	937 ms	263060 KiB

knapsack

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

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

    int W, n;
    cin >> W >> n;

    vector<vector<int>> groups(501);

    for(int i = 0; i < n; i++){
        int v, w, cnt;
        cin >> v >> w >> cnt;

        while(cnt--){
            groups[w].push_back(v);
        }
    }

    vector<int> dp(W+1, 0);

    for(int w = 1; w <= 500; w++){
        if(groups[w].empty()) continue;

        auto &vals = groups[w];
        sort(vals.rbegin(), vals.rend());

        vector<int> prefix(vals.size()+1, 0);
        for(int i = 0; i < vals.size(); i++){
            prefix[i+1] = prefix[i] + vals[i];
        }

        for(int j = W; j >= 0; j--){
            for(int t = 1; t <= (int)vals.size(); t++){
                if(j >= w*t){
                    dp[j] = max(dp[j], dp[j - w*t] + prefix[t]);
                }
            }
        }
    }

    cout << dp[W];
}

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