Submission #966892

#	Time	Username	Problem	Language	Result	Execution time	Memory
966892		Jomnoi	Knapsack (NOI18_knapsack)	C++17	100 / 100	215 ms	19540 KiB

knapsack

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

const int MAX_W = 2005;

int dp[MAX_W][MAX_W];
vector <pair <int, int>> items[MAX_W];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int S, N;
    cin >> S >> N;

    while (N--) {
        int v, w, k;
        cin >> v >> w >> k;

        items[w].emplace_back(v, k);
    }

    for (int w = 1; w <= S; w++) sort(items[w].begin(), items[w].end(), greater <pair <int, int>> ());
    for (int i = 1; i <= S; i++) {
        for (int w = 0; w <= S; w++) {
            int cur_w = w, cur_v = 0;
            dp[i][w] = dp[i - 1][w];
            for (auto [v, k] : items[i]) {
                int cur_k = k;
                while (cur_w - i >= 0 and cur_k > 0) {
                    dp[i][w] = max(dp[i][w], dp[i - 1][cur_w - i] + cur_v + v);
                    cur_v += v;
                    cur_w -= i;
                    cur_k--;
                }
            }
        }
    }
    cout << dp[S][S];
    return 0;
}

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