Submission #609769

#	Time	Username	Problem	Language	Result	Execution time	Memory
609769		lucas_joel_han	Knapsack (NOI18_knapsack)	C++14	100 / 100	150 ms	35084 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define fi first
#define se second
#define sz(v) int(v.size())

int main() {
    int lim, n;
    cin >> lim >> n;
    map<int, vector<pii>> list_of_items;
    for (int i = 0; i < n; i++) {
        int val, weight, cnt;
        cin >> val >> weight >> cnt;
        list_of_items[weight].emplace_back(val, cnt);
    }
    vector<vector<ll>> dp(sz(list_of_items) + 1, vector<ll>(lim + 1, -1000));
    dp[0][0] = 0;
    int i = 1;
    for (auto &[weight, items] : list_of_items) {
        sort(items.begin(), items.end(), greater<pii>());
        for (int j = 0; j <= lim; j++) {
            dp[i][j] = dp[i - 1][j];
            int cps = 0, items_idx = 0, used = 0;
            long long profit = 0;
            while ((cps + 1) * weight <= j && items_idx < sz(items)) {
                cps++;
                profit += items[items_idx].fi;
                if (dp[i - 1][j - cps * weight] != -1000) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - cps * weight] + profit);
                }
                used++;
                if (used == items[items_idx].se) {
                    used = 0, items_idx++;
                }
            }
        }
        i++;
    }
    cout << *max_element(dp.back().begin(), dp.back().end()) << '\n';
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:21:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for (auto &[weight, items] : list_of_items) {
      |                ^

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