제출 #1290022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290022		m_a_d	Knapsack (NOI18_knapsack)	C++20	100 / 100	98 ms	5444 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

#define int long long

int32_t main() {
    int s, n;
    cin >> s >> n;
    int items[n][3];
    for(int i=0; i<n; ++i) cin >> items[i][0] >> items[i][1] >> items[i][2], items[i][2]=min(items[i][2], s/items[i][1]);
    priority_queue<pair<int, int>> pque[s+1];
    for(int i=0; i<n; ++i) pque[items[i][1]].push({items[i][0], items[i][2]});
    vector<pair<int, int>> final_items;
    for(int i=1; i<=s; ++i) {
        int amount=0;
        while(!pque[i].empty() && amount+1<=s/i) {
            final_items.push_back({i, pque[i].top().first});
            auto top=pque[i].top();
            pque[i].pop();
            if(top.second>1) pque[i].push({top.first, top.second-1});
            amount++;
        }
    }
    int knapsack[s+1]={};
    int sizes=final_items.size();
    for(int i=0; i<sizes; ++i) {
        //cout << final_items[i].first << " " << final_items[i].second;
        for(int j=s; j>=0; --j) {
            if(final_items[i].first+j<=s) {
                knapsack[final_items[i].first+j]=max(knapsack[final_items[i].first+j], knapsack[j]+final_items[i].second);
            }
        }
    }
    int ans=0;
    for(auto &elem:knapsack) {
        //cout << elem << " ";
        ans=max(ans, elem);
    }
    cout << ans;
    return 0;
}

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