제출 #1284955

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284955		RomanLeshchuk	Knapsack (NOI18_knapsack)	C++20	100 / 100	90 ms	1756 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int s, n;
    cin >> s >> n;

    vector<vector<pair<int, int>>> perW(s + 1);
    for (int i = 0; i < n; ++i)
    {
        int v, w, k;
        cin >> v >> w >> k;
        perW[w].emplace_back(v, k);
    }

    vector<pair<int, int>> items{};
    for (int i = 1; i <= s; ++i)
    {
        sort(perW[i].begin(), perW[i].end(), greater<pair<int, int>>{});
        int wPerType = 0;
        for (pair<int, int> item : perW[i])
        {
            for (int j = 0; j < item.second; ++j)
            {
                wPerType += i;
                if (wPerType > s)
                {
                    break;
                }
                items.emplace_back(i, item.first);
            }
            if (wPerType > s)
            {
                break;
            }
        }
    }

    vector<int> dp(s + 1);
    for (int i = 0; i < items.size(); ++i)
    {
        for (int j = s; j >= items[i].first; --j)
        {
            dp[j] = max(dp[j], dp[j - items[i].first] + items[i].second);
        }
    }

    cout << dp[s] << '\n';

    return 0;
}

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