Submission #907693

#	Time	Username	Problem	Language	Result	Execution time	Memory
907693		Ca7Ac1	Knapsack (NOI18_knapsack)	C++17	100 / 100	54 ms	616 KiB

knapsack

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <math.h>

#define ll int
#define pll pair<ll, ll>

using namespace std;

int main()
{   
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll s;
    ll n;
    cin >> s >> n;

    vector<priority_queue<ll, vector<ll>, greater<ll>>> arr(s, priority_queue<ll, vector<ll>, greater<ll>>());
    for (ll i = 0; i < n; i++)
    {
        ll v;
        ll w;
        ll k;
        cin >> v >> w >> k;
        
        while (arr[w - 1].size() * w <= s && k > 0)
        {
            arr[w - 1].push(v);
            
            k--;
        }

        while (arr[w - 1].top() < v && k > 0)
        {
            arr[w - 1].pop();
            arr[w - 1].push(v);

            k--;
        }
    }

    vector<ll> dp(s + 1, 0);
    for (ll i = 1; i <= s; i++)
    {
        auto &values = arr[i - 1];

        while (!values.empty())
        {
            ll curr = values.top();
            values.pop();

            for (ll j = s; j >= 0; j--)
            {
                if (j + i <= s)
                {
                    dp[j + i] = max(dp[j + i], dp[j] + curr);
                }
            }
        }
    }

    ll sol = 0;
    for (ll i : dp)
    {
        sol = max(sol, i);
    }

    cout << sol << '\n';

    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:33:38: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |         while (arr[w - 1].size() * w <= s && k > 0)
      |                ~~~~~~~~~~~~~~~~~~~~~~^~~~

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