Submission #892097

#	Time	Username	Problem	Language	Result	Execution time	Memory
892097		cogentcoder73	Knapsack (NOI18_knapsack)	C++17	12 / 100	0 ms	440 KiB

knapsack

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

struct Item {
    int V, W, K;
    Item() {
        V = 0;
        W = 0;
        K = 0;
    }
    Item(int v, int w, int k) {
        V = v;
        W = w;
        K = k;
    }
    bool operator< (Item other) {
        if (W != other.W) return W < other.W;
        return V < other.V;
    }
};

int main() {
    int S, N;
    cin >> S >> N;

    Item items[N];
    for (int i = 0; i < N; i++) {
        cin >> items[i].V >> items[i].W >> items[i].K;
        items[i].K = min(items[i].K, S/items[i].W);
    }

    sort(items, items + N);

    vector<pair<int, int>> itemList[S + 1];
    int ind = 0;
    int curW, delW;
    for (int w = 1; w <= S; w++) {
        itemList[w].clear();
        curW = 0;
        while (ind < N && items[ind].W == w && curW < S) {
            delW = min(items[ind].K, S - curW);
            itemList[w].push_back({delW, items[ind].V});
            curW += delW;
            ind++;
        }
    }

    int dp[S + 1];
    fill(dp, dp + S + 1, 0);

    for (int w = 1; w <= S; w++) {
        for (pair<int, int> i : itemList[w]) {
            for (int curI = 0; curI < i.first; curI++) {
                for (curW = S - w; curW >= 0; curW--) {
                    dp[curW + w] = max(dp[curW + w], dp[curW] + i.second);
                }
            }
        }
    }

    cout << *max_element(dp, dp + S + 1) << "\n";
    return 0;
}

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