제출 #1286271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286271		Soju	Knapsack (NOI18_knapsack)	C++20	29 / 100	1098 ms	84352 KiB

knapsack

#pragma GCC optimize("O3,inline,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).begin(), (v).end()
#define debug cerr << "[DEBUG] "

const char wp = ' ';
const char nl = '\n';

void kebin() {
    ll s, n;
    cin >> s >> n;

    vector<tuple<ll, ll, ll>> arr(n);
    for (auto &[a, b, c] : arr) {
        cin >> a >> b >> c;
        // {value, weight, number (or copies)}
    }

    vector<ll> ans(s+1);
    vector<pair<ll,ll>> dp;
    dp.push_back({0, 0});

    // prolly the dumbest idea
    ll res = 0;
    for (auto [val, wei, cnt] : arr) {
        for (int i = 1; i <= cnt and i * wei <= s; i++) {
            auto nw = vector<pair<ll,ll>>();
            for (auto [acc_w, acc_val] : dp) {
                ll nwei = acc_w + wei;
                if (nwei > s) continue;

                if (ans[nwei] < acc_val + val) {
                    ans[nwei] = acc_val + val;
                    res = max(res, ans[nwei]);
                    nw.push_back({nwei, acc_val + val});
                }
            }
            dp.insert(dp.end(), all(nw));
        }
    }
    cout << res << nl;
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--) kebin();
}

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