Submission #1188015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188015		mehmetkagan	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	488 KiB

knapsack

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int S, N;
    cin >> S >> N;
    vector<int> dp(S + 1, 0);

    while (N--) {
        int v, w, k;
        cin >> v >> w >> k;
        int cap = S / w;

        if (k > cap) {
            // unbounded knapsack
            for (int j = w; j <= S; ++j) {
                int val = dp[j - w] + v;
                if (val > dp[j]) dp[j] = val;
            }
        } else {
            // bounded: sliding window DP for each modulo class
            for (int r = 0; r < w; ++r) {
                deque<pair<int, int>> dq;
                for (int m = 0, j = r; j <= S; ++m, j += w) {
                    int f = dp[j] - m * v;
                    while (!dq.empty() && dq.back().second <= f)
                        dq.pop_back();
                    dq.emplace_back(m, f);
                    while (!dq.empty() && dq.front().first < m - k)
                        dq.pop_front();
                    dp[j] = dq.front().second + m * v;
                }
            }
        }
    }

    int res = 0;
    for (int x : dp) if (x > res) res = x;
    cout << res << '\n';
    return 0;
}

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