Submission #1086094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086094		lukasuliashvili	Knapsack (NOI18_knapsack)	C++17	37 / 100	1 ms	436 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to solve the bounded knapsack problem
int knapsack(int S, int N, vector<tuple<int, int, int>>& items) {
    // dp[w] will store the max value we can achieve with weight w
    vector<int> dp(S + 1, 0);
    
    // Process each item (V: value, W: weight, K: quantity)
    for (const auto& item : items) {
        int V, W, K;
        tie(V, W, K) = item;
        
        int count = 1;
        while (K > 0) {
            int current_count = min(count, K);
            K -= current_count;
            int item_weight = current_count * W;
            int item_value = current_count * V;
            
            // Update dp array using 0/1 knapsack for this batch of items
            for (int weight = S; weight >= item_weight; --weight) {
                dp[weight] = max(dp[weight], dp[weight - item_weight] + item_value);
            }
            
            count *= 2;
        }
    }
    
    // The maximum value we can achieve with total weight <= S
    return *max_element(dp.begin(), dp.end());
}

int main() {
    int S, N;
    // Read S (maximum weight) and N (number of item types)
    cin >> S >> N;
    
    // Store the items as tuples (value, weight, quantity)
    vector<tuple<int, int, int>> items(N);
    
    for (int i = 0; i < N; ++i) {
        int V, W, K;
        cin >> V >> W >> K;
        items[i] = make_tuple(V, W, K);
    }
    
    // Solve the problem
    cout << knapsack(S, N, items) << endl;
    
    return 0;
}

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