Submission #1158343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158343		t6stks	Knapsack (NOI18_knapsack)	C++20	100 / 100	939 ms	16800 KiB

knapsack

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(), x.end()

using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vii = vector<pii>;
using vll = vector<pll>;

void sol() {
    int s, n;
    cin >> s >> n;
    vector<pair<int, ll>> items(1);
    for (int i = 0; i < n; i++) {
        int v, w, k;
        cin >> v >> w >> k;
        k = min(k, s / w);
        for (int j = 1; j < k; j <<= 1) {
            if (1ll * w * j <= s)
                items.push_back({w * j, 1ll * v * j});
            k-=j;
        }
        items.push_back({w * k, v * k});
    }
    int m = SZ(items) - 1;
    vl dp(s + 1);
    for (int i = 1; i <= m; i++) {
        auto &[w, v] = items[i];
        for (int j = s - w; j >= 0; j--) {
            dp[j + w] = max(dp[j + w], dp[j] + v);
        }
    }
    cout << dp[s] << '\n';
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    sol();
}

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