Submission #1295526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295526		michaeltaranik	Knapsack (NOI18_knapsack)	C++17	73 / 100	1093 ms	588 KiB

knapsack

#include <iostream>
#include <limits.h>
#include <vector>
#include <array>

using namespace std;
typedef long long ll;

// 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() {
    ll s, n;
    cin >> s >> n;
    vector<ll> dp(s+1, 0);

    for (ll i = 0; i < n; ++i) {
        ll v, w, q;
        cin >> v >> w >> q;
        
        // fucking binary optimization
        for (ll k = 1; q > 0; k <<= 1) {
            ll take = min(k, q);
            ll chunkV = take * v;
            ll chunkW = take * w;

            if (chunkW <= s) {
              for (ll j = s; j >= chunkW; --j) {
                dp[j] = max(dp[j], dp[j - chunkW] + chunkV);
              }
            }
            q -= take;
        }
    }

    cout << dp[s] << endl;
}

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

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