Submission #1264975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264975		marshziin	Knapsack (NOI18_knapsack)	C++20	100 / 100	86 ms	34376 KiB

knapsack

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

#define int long long
#define pii pair<int,int>

const long long NEG = (long long)-9e18;

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    int s, n;
    if (!(cin >> s >> n)) return 0;
    map<int, vector<pii>> W;
    for (int i = 0; i < n; ++i) {
        int v, w, k; cin >> v >> w >> k;
        W[w].push_back({v, k});
    }

    int groups = (int)W.size();
    vector<vector<long long>> dp(groups + 1, vector<long long>(s + 1, NEG));
    dp[0][0] = 0;

    int cur = 1;
    for (auto [weight, items] : W) {
        sort(items.begin(), items.end(), greater<pii>());

        dp[cur][0] = dp[cur - 1][0];

        for (int i = 1; i <= s; ++i) {
            dp[cur][i] = dp[cur - 1][i];

            int cnt = 0;
            int sum = weight, pos = 0, cum = 0;
            while (sum <= s && pos < (int)items.size()) {
                if (cnt == items[pos].second) {
                    pos++;
                    cnt = 0;
                    continue;
                }

                cum += items[pos].first;
                if (i >= sum && dp[cur - 1][i - sum] != NEG) {
                    dp[cur][i] = max(dp[cur][i], dp[cur - 1][i - sum] + cum);
                }
                sum += weight;
                cnt++;
            }
        }
        cur++;
    }

    long long res = 0;
    for (int i = 1; i <= s; ++i) res = max(res, dp[cur - 1][i]);
    cout << res << '\n';
    return 0;
}

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