Submission #1295518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295518		michaeltaranik	Knapsack (NOI18_knapsack)	C++17	0 / 100	171 ms	327680 KiB

knapsack

#include <iostream>
#include <limits.h>
#include <vector>
#include <array>
#include <bits/stdc++.h>

using namespace std;
#define V 0
#define W 1
#define K 2

int solvedp(int goal, vector<array<int, 2>>& items, vector<vector<int>>& memo, int idx) {
    if (goal < 0) return INT_MIN;
    if (goal == 0 || idx >= items.size()) return 0;
    if (memo[goal][idx] != -1) return memo[goal][idx];

    int skip = solvedp(goal, items, memo, idx+1); 
    int take = solvedp(goal - items[idx][W], items, memo, idx+1);
    if (take >= 0) {
        take += items[idx][V];
    }
    int best = max(skip, take);

    memo[goal][idx] = best;
    return best;
}

void solve() {
    int s, n;
    cin >> s >> n;
    vector<array<int, 3>> items(n);
    
    for (int i = 0; i < n; ++i) {
        cin >> items[i][0];
        cin >> items[i][1];
        cin >> items[i][2];
    }
    vector<array<int, 2>> tms;
    for (auto itm: items) {
        for (int i = 0; i < itm[K]; ++i) {
            tms.push_back({itm[V], itm[W]});
        }
    }
    vector<vector<int>> memo(s+1, vector<int>(tms.size(), -1));
    cout << solvedp(s, tms, memo, 0) << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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