Submission #892106

#	Time	Username	Problem	Language	Result	Execution time	Memory
892106		cogentcoder73	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	348 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;
    }
};

bool comp(Item i1, Item i2) {
    double rat1 = (i1.V * 1.0)/i1.W;
    double rat2 = (i2.V * 1.0)/i2.W;
    if (abs(rat1 - rat2) > 1e-9) {
        return rat1 > rat2;
    }
    return i1.V > i2.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);

    vector<Item> decVal;
    for (int w = 1; w <= S; w++) {
        for (pair<int, int> p : itemList[w]) decVal.push_back(Item(p.second, w, p.first));
    }

    sort(decVal.begin(), decVal.end(), comp);

    for (Item i : decVal) {
        for (int k = 0; k < i.K; k++) {
            for (int w = S - i.W; w >= 0; w--) {
                dp[w + i.W] = max(dp[w + i.W], dp[w] + i.V);
            }
        }
    }

    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