제출 #1330972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1330972		silver_bullet	Knapsack (NOI18_knapsack)	C++17	100 / 100	38 ms	880 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
const int maxW = (int)2e3 + 2;
priority_queue<int,vector<int>,greater<int>> pq[maxW];
long long dp[maxW];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int W,n;
    cin >> W >> n;
    for(int i=1;i<=n;++i)
    {
        int v,w,k;
        cin >> v >> w >> k;
        while(pq[w].size() < W / w && k > 0)
        {
            --k;
            pq[w].push(v);
        }
        if(pq[w].size() == W / w )
        {
            while(k && pq[w].top() < v)
            {
                --k;
                pq[w].pop();
                pq[w].push(v);
            }
        }
    }
    vector<array<int,2>> a;
    a.clear();
    for(int w=1;w<=W;++w) 
    {
        while(pq[w].size())
        {
            a.push_back({w,pq[w].top()});
            pq[w].pop();
        }
    }
    for(auto x : a)
    {
        for(int i=W;i>=x[0];--i)
        dp[i] = max(dp[i],dp[i-x[0]] + x[1]);
    }
    cout << dp[W];
}

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