Submission #1241926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241926		bach25089	Knapsack (NOI18_knapsack)	C++20	100 / 100	109 ms	33256 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, s;
    cin >> n >> s;
    map<int, vector<pair<int, int>>> mp;
    for (int i = 0; i < s; i++)
    {
        int v, w, k;
        cin >> v >> w >> k;
        if (w <= n && k > 0)
        {
            mp[w].push_back({v, k});
        }
    }
    vector<vector<long long>> dp(mp.size() + 1, vector<long long>(n + 1, INT_MIN));
    dp[0][0] = 0;
    int id = 1;
    for (auto &[w, t1] : mp)
    {
        sort(t1.begin(), t1.end(), greater<pair<int, int>>());
        for (int i = 0; i <= n; i++)
        {
            dp[id][i] = dp[id - 1][i];
            int cnt = 0, vt = 0, ok = 0;
            long long sum = 0;
            while ((cnt + 1) * w <= i && vt < t1.size())
            {
                cnt++;
                sum += t1[vt].first;
                if (dp[id - 1][i - cnt * w] != INT_MIN) dp[id][i] = max(dp[id][i], dp[id - 1][i - cnt * w] + sum);
                ok++;
                if (ok == t1[vt].second)
                {
                    ok = 0;
                    vt++;
                }
            }
        }
        id++;
    }
    cout << *max_element(dp.back().begin(), dp.back().end());
}

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