Submission #1157813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157813		marcus06	Knapsack (NOI18_knapsack)	C++20	100 / 100	137 ms	33200 KiB

knapsack

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

#ifdef LOCAL
#include </home/marcus06/vimcp/Library/debug.h>
#else
#define debug(...) 
#endif

void solve() {
    int S, N; cin >> S >> N;
    vector <vector <pair <int, int>>> groups(S + 1);
    for (int i = 0; i < N; ++i) {
        int v, w, k;
        cin >> v >> w >> k;
        groups[w].emplace_back(v, k);
    }

    for (int i = 1; i <= S; ++i) {
        sort(groups[i].begin(), groups[i].end(), greater <pair <int, int>>());
    }

    vector <vector <lli>> dp(S + 1, vector <lli> (S + 1, 0));
    for (int i = 1; i <= S; ++i) {
        dp[i] = dp[i - 1];
        if (groups[i].empty()) continue;

        //only consider S / i items from this set
        for (int j = S; j >= 0; --j) {
            int cur_w = 0;
            lli cur_v = 0;
            for (auto [v, k]: groups[i]) {
                while (k > 0 && cur_w <= j) {
                    cur_w += i;
                    cur_v += v;
                    --k;
                    if (j >= cur_w) dp[i][j] = max(dp[i][j], dp[i - 1][j - cur_w] + cur_v);
                }
            }
        }
    }

    lli ans = *max_element(dp[S].begin(), dp[S].end());
    cout << ans << '\n';
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
    auto begin = std::chrono::high_resolution_clock::now();
#endif

    int tt = 1;
    while (tt--) {
        solve();
    }

#ifdef LOCAL
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    std::cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
#endif
    return 0;
}

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