제출 #1146832

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146832		amin5555	Knapsack (NOI18_knapsack)	C++20	100 / 100	106 ms	33256 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;
using ll = long long;


int main(){
    int S, N;
    cin >> S >> N;
    map<int, vector<pair<int, int>>> by_weights;
    for(int i = 0; i < N; i++){
        int val, weight, amt;
        cin >> val >> weight >> amt;
        by_weights[weight].push_back({val, amt});
    }

    vector<vector<ll>> best_at(by_weights.size() + 1, vector<ll>(S + 1, INT32_MIN));
    best_at[0][0] = 0;
    int at = 1;
    for(auto &[w, items]: by_weights){
        sort(items.begin(), items.end(), greater<pair<int, int>>());
        for(int i = 0; i <= S; i++){
            best_at[at][i] = best_at[at - 1][i];
            int copies = 0;
            ll profit = 0;
            int curr_used = 0;
            int type_at = 0;

            while((copies + 1) * w <= i && type_at < items.size()){
                copies++;
                profit += items[type_at].first;
                if(best_at[at - 1][i - copies * w] != INT32_MIN){
                    best_at[at][i] = max(best_at[at][i], best_at[at - 1][i - copies * w] + profit);
                }

                curr_used++;
                if(curr_used == items[type_at].second){
                    curr_used = 0;
                    type_at++;
                }
            }
        }
        at++;
    }

    cout << *max_element(best_at.back().begin(), best_at.back().end()) << '\n';
}

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