Submission #585730

#	Time	Username	Problem	Language	Result	Execution time	Memory
585730		imtiyazrasool92	Knapsack (NOI18_knapsack)	C++17	12 / 100	5 ms	340 KiB

knapsack

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>

// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

using namespace std;

#ifdef imtiyazrasool92
#include "algos/debug.h"
#else
#define dbg(...) 92
#endif

void run_case() {
    int S, N;
    cin >> S >> N;

    // vi,wi,ki
    vector<array<int64_t, 3>> A(N);
    for (auto &[x, y, z] : A)
        cin >> x >> y >> z;

    // store number of times current element is used,max score can achieve
    vector<array<int64_t, 2>> dp(S + 1, { -1, -1});
    dp[0] = {0, 0};

    for (int i = 0; i < N; i++) {
        for (int j = A[i][1]; j <= S && A[i][2] > 0; j++) {
            int reach = j - A[i][1];
            if (dp[reach] != array<int64_t, 2> { -1, -1}) {
                array<int64_t, 2> can_be = dp[reach];
                can_be[1] += A[i][0];
                can_be[0]++;
                if (can_be[0] <= A[i][2] && can_be[1] > dp[j][1]) {
                    dp[j] = can_be;
                }
            }
        }
        for (int j = 0; j <= S; j++)
            if (dp[j] != array<int64_t, 2> { -1, -1})
                dp[j][0] = 0;
    }

    int64_t answer = 0;
    for (int s = 0; s <= S; s++)
        answer = max<int64_t>(answer, dp[s][1]);

    cout << answer;
}

int32_t main() {
    ios::sync_with_stdio(false);
#ifndef imtiyazrasool92
    cin.tie(nullptr);
#endif

    int tests = 1;
    // cin >> tests;

    while (tests--) {
        run_case();
        cout << '\n';
    }

    return 0;
}

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