Submission #883361

#	Time	Username	Problem	Language	Result	Execution time	Memory
883361		Azzmi	Knapsack (NOI18_knapsack)	C++14	100 / 100	764 ms	9160 KiB

knapsack

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

struct Item
{
    int v, w, k;
};

int s, n;
Item store[100'000];

ll dp[2001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> s >> n;
    for (int i = 0; i < n; ++i) {
        cin >> store[i].v >> store[i].w >> store[i].k;
    }
    sort(store, store + n, [](Item &a, Item &b) {
        if (a.w != b.w) return a.w < b.w;
        return a.v > b.v;
    });

    vector<pair<int, int>> store_simplified;

    int current_weight = store[0].w;
    int accumulated_freq = 0;
    for (int i = 0; i < n; ++i) {
        if (current_weight != store[i].w) {
            current_weight = store[i].w;
            accumulated_freq = 0;
        }
        int given = min({2000 / current_weight, 2000 - accumulated_freq, store[i].k});
        if (given > 0) {
            for (int j = 0; j < given; ++j) {
                store_simplified.push_back({store[i].v, current_weight});
            }
        }
        accumulated_freq += given;
    }

    n = store_simplified.size();
    for (int i = 0; i < n; ++i) {
        for (int w = s; w >= 0; --w) {
            if (w - store_simplified[i].second >= 0) {
                dp[w] = max(dp[w], dp[w - store_simplified[i].second] + store_simplified[i].first);
            }
        }
    }
    cout << dp[s] << '\n';
    return 0;
}

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