Submission #1086124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086124		lukasuliashvili	Knapsack (NOI18_knapsack)	C++17	73 / 100	4 ms	1112 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];
    
    // Process in powers of two
    for (int i = 1; i <= count; i *= 2) {
        long long num = min(i, count); // Take the minimum of current power of two and remaining count
        count -= num;
        
        // Update dp array in reverse order
        for (int j = s; j >= num * weight; j--) {
            dp[j] = max(dp[j], dp[j - num * weight] + num * value);
        }
    }

    // Process the remaining items
    if (count > 0) {
        for (int j = s; j >= count * weight; j--) {
            dp[j] = max(dp[j], dp[j - count * weight] + count * value);
        }
    }
}

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