Submission #1158349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158349		t6stks	Knapsack (NOI18_knapsack)	C++20	100 / 100	88 ms	9652 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<vector<ll>> items_by_weight(s + 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_by_weight[w * j].push_back(1ll * v * j);
            k-=j;
        }
        if (1ll * w * k <= s)
            items_by_weight[w * k].push_back(1ll * v * k);
    }
    vector<pair<int, ll>> items(1);
    for (int i = 1; i <= s; i++) {
        sort(ALL(items_by_weight[i]), greater<ll>());
        for (int j = 0; j < SZ(items_by_weight[i]) && (j + 1) * i <= s; j++) {
            items.push_back({i, items_by_weight[i][j]});
        }
    }
    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