Submission #1086125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086125		lukasuliashvili	Knapsack (NOI18_knapsack)	C++17	73 / 100	4 ms	1116 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

const int MAX_S = 10005;
long long v[MAX_S], w[MAX_S];
long long dp[MAX_S];
int k[MAX_S];

void process_item(int idx, int s) {
    long long value = v[idx];
    long long weight = w[idx];
    int count = k[idx];
    
    // Convert the problem to multiple 0/1 knapsack problems
    int power = 1;
    while (count > 0) {
        int num = min(power, count);
        count -= num;
        // Process `num` items of this type
        for (int j = s; j >= num * weight; j--) {
            dp[j] = max(dp[j], dp[j - num * weight] + num * value);
        }
        power *= 2; // Move to the next power of 2
    }
}

int main() {
    int s, n;
    cin >> s >> n;

    // Read inputs
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i] >> k[i]; // v[i] = value, w[i] = weight, k[i] = max times we can take item i
    }

    // Initialize dp array
    fill(dp, dp + s + 1, 0);

    // Process each item
    for (int i = 1; i <= n; i++) {
        process_item(i, s);
    }

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

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