Submission #373388

#	Time	Username	Problem	Language	Result	Execution time	Memory
373388		arujbansal	Knapsack (NOI18_knapsack)	C++17	100 / 100	70 ms	5480 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> 
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
using ll = long long;

const int MAXN = 1e5 + 5;
const ll INF = 1e18;

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

    vector<pair<ll, ll>> items;

    for (int i = 0; i < N; i++) {
        ll V, W, K;
        cin >> V >> W >> K;

        if (W > S) continue;

        ll inc = 1;
        while (inc <= K) {
            items.emplace_back(V * inc, W * inc);
            inc *= 2;
        }

        items.pop_back();

        inc /= 2;
        inc--;

        if (K == inc) continue;
        items.emplace_back(V * (K - inc), W * (K - inc));
    }

    vector<ll> dp(S + 1, -INF);
    dp[0] = 0;

    for (const auto &[val, wt] : items) {
        if (S - wt < 0) continue;
        for (int i = S - wt; i >= 0; i--) {
            dp[i + wt] = max(dp[i + wt], dp[i] + val);
        }
    }

    cout << *max_element(all(dp));
}

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

    vector<pair<ll, ll>> A[S + 1];

    for (int i = 0; i < N; i++) {
        ll V, W, K;
        cin >> V >> W >> K;

        A[W].emplace_back(V, K);
    }

    vector<pair<ll, ll>> items;

    for (int i = 1; i <= S; i++) {
        sort(all(A[i]), greater<>());

        int take = S / i + 1, j = 0;
        while (take && j < sz(A[i])) {
            if (A[i][j].second == 0) {
                j++;
                continue;
            }

            A[i][j].second--;
            take--;
            items.emplace_back(A[i][j].first, i);
        }
    }

    vector<ll> dp(S + 1, -INF);
    dp[0] = 0;

    for (const auto &[val, wt] : items) {
        if (S - wt < 0) continue;
        for (int i = S - wt; i >= 0; i--) {
            dp[i + wt] = max(dp[i + wt], dp[i] + val);
        }
    }

    cout << *max_element(all(dp));
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // subtask4();
    solve();
}

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