Submission #1199287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199287		gugug	Knapsack (NOI18_knapsack)	C++20	49 / 100	2 ms	328 KiB

knapsack

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

using namespace std;

struct Item {
    int value;
    int weight;
    long long quantity;
};

long long knapsack_single_item(int S, const Item& item) {
    return static_cast<long long>(item.value) * min(item.quantity, static_cast<long long>(S / item.weight));
}

long long knapsack_01(int S, const vector<Item>& items) {
    vector<long long> dp(S + 1, 0);
    
    for (const auto& item : items) {
        for (int s = S; s >= item.weight; s--) {
            dp[s] = max(dp[s], dp[s - item.weight] + item.value);
        }
    }
    
    return dp[S];
}

long long knapsack_bounded(int S, const vector<Item>& items) {
    vector<long long> dp(S + 1, 0);
    
    for (const auto& item : items) {
        for (int s = S; s >= item.weight; s--) {
            for (int count = 1; count <= min(item.quantity, static_cast<long long>((s / item.weight))); count++) {
                dp[s] = max(dp[s], dp[s - count * item.weight] + count * static_cast<long long>(item.value));
            }
        }
    }
    
    return dp[S];
}

long long knapsack_large_quantities(int S, const vector<Item>& items) {
    vector<long long> dp(S + 1, 0);
    
    for (const auto& item : items) {
        if (item.value == 0 || item.weight == 0 || item.weight > S) {
            continue;
        }
        
        vector<pair<long long, int>> binary_items;
        long long remaining = item.quantity;
        long long q = 1;
        
        while (remaining > 0) {
            if (remaining & 1) { 
                long long package_value = static_cast<long long>(item.value) * q;
                int package_weight = item.weight * q;
                
                if (package_weight <= S) {
                    binary_items.push_back({package_value, package_weight});
                }
            }
            
            q *= 2;
            
            remaining >>= 1;
            
            if (item.weight * q > S) {
                break;
            }
        }
        
        for (const auto& [package_value, package_weight] : binary_items) {
            for (int s = S; s >= package_weight; s--) {
                dp[s] = max(dp[s], dp[s - package_weight] + package_value);
            }
        }
    }
    
    return dp[S];
}

long long solve_knapsack(int S, const vector<Item>& items) {
    int N = items.size();
    
    if (N == 1) {
        return knapsack_single_item(S, items[0]);
    }
    
    bool all_quantity_one = true;
    for (const auto& item : items) {
        if (item.quantity != 1) {
            all_quantity_one = false;
            break;
        }
    }
    if (all_quantity_one) {
        return knapsack_01(S, items);
    }
    
    bool all_small_quantities = true;
    for (const auto& item : items) {
        if (item.quantity > 10) {
            all_small_quantities = false;
            break;
        }
    }
    if (N <= 100 && all_small_quantities) {
        return knapsack_bounded(S, items);
    }
    
    return knapsack_large_quantities(S, items);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int S, N;
    cin >> S >> N;
    
    vector<Item> items(N);
    for (int i = 0; i < N; i++) {
        cin >> items[i].value >> items[i].weight >> items[i].quantity;
    }
    
    long long result = solve_knapsack(S, items);
    cout << result << endl;
    
    return 0;
}

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