Submission #1021091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021091		urejgi	Knapsack (NOI18_knapsack)	C++17	100 / 100	89 ms	36436 KiB

knapsack

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#define int long long
using namespace std;

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int s, n; cin >> s >> n;
    map<int, vector<pair<int, int>>> groups;
    for (int i = 0; i < n; ++i) {
        int v, w, k;
        cin >> v >> w >> k;
        if (w <= s && k > 0) {
            groups[w].push_back(make_pair(v, k));
        }
    }
    int at = 1;
    vector<vector<long long>> dp(groups.size() + 1, vector<long long>(s + 1, INT32_MIN));
    dp[0][0] = 0;
    for (auto &[KEY, VALUE] : groups) {
        sort(VALUE.begin(), VALUE.end(), greater<pair<int, int>>());
        for (int i = 0; i <= s; ++i) {
            dp[at][i] = dp[at - 1][i];
            int copies = 0, type = 0, curused = 0;
            long long profit = 0;
            while ((copies + 1) * KEY <= i && type < VALUE.size()) {
                copies++;
                profit += VALUE[type].first;
                if (dp[at - 1][i - copies * KEY] != INT32_MIN) {
                    dp[at][i] = max(dp[at][i], dp[at - 1][i - copies * KEY] + profit);
                }
                curused++;
                if (curused == VALUE[type].second) {
                    curused = 0;
                    type++;
                }
            }
        }
        at++;
    }
    cout << *max_element(dp.back().begin(), dp.back().end()) << '\n';
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:28:52: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |             while ((copies + 1) * KEY <= i && type < VALUE.size()) {
      |                                               ~~~~~^~~~~~~~~~~~~~

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