#1083954 (C++17) No.2026 Yet Another Knapsack Problem

• 問題: No.2026 Yet Another Knapsack Problem
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:10:54
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,425 bytes
• コンパイル時間: 1,042 ms
• コンパイル使用メモリ: 91,684 KB
• 実行使用メモリ: 16,072 KB
• 最終ジャッジ日時: 2025-05-14 13:13:32
• 合計ジャッジ時間: 73,304 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 35 TLE * 1 -- * 6

ソースコード

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

using namespace std;

// Define long long for convenience
typedef long long ll;

// Define a very small negative value to represent infinity (unreachable states).
// The maximum possible value sum is approximately N * 10^9 = 2500 * 10^9 = 2.5 * 10^12.
// The minimum possible value sum is approximately N * (-10^9) = -2.5 * 10^12.
// Choose NINF sufficiently small. -3 * 10^18 should be safe.
const ll NINF = -3e18; 

int main() {
    // Use fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N; // Number of item types and maximum weight capacity
    cin >> N;

    // Store counts and values for each item type
    vector<int> counts(N + 1);
    vector<ll> values(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> counts[i] >> values[i];
    }

    // Initialize DP table. dp[k][w] stores the maximum value achievable
    // using exactly k items with a total weight of exactly w.
    vector<vector<ll>> dp(N + 1, vector<ll>(N + 1, NINF));
    
    // Base case: 0 items, 0 weight results in 0 value.
    dp[0][0] = 0; 

    // Iterate through each item type from 1 to N
    for (int i = 1; i <= N; ++i) {
        int c_i = counts[i]; // Number of items of type i available
        ll v_i = values[i];  // Value of one item of type i
        int weight = i;       // Weight of one item of type i
        
        // Basic check: Item weight must be positive (guaranteed by constraints 1 <= i <= N).
        if (weight == 0) continue; 

        // Create a temporary DP table `next_dp` initialized with the current `dp` state.
        // This ensures that updates for item type `i` are based on the results
        // from processing items 1 to `i-1`. Using `std::move` later optimizes assignment.
        vector<vector<ll>> next_dp = dp; 

        // Apply the monotonic queue optimization for bounded knapsack.
        // Iterate through all possible remainders `r` when weight `w` is divided by `weight`.
        for (int r = 0; r < weight; ++r) {
            
            // Calculate the maximum possible quotient `q` such that `q * weight + r <= N`.
            int max_q_for_r = (N - r) / weight;
            // If `N < r`, then `max_q_for_r` can be negative. No states to process for this `r`.
            if (max_q_for_r < 0) continue; 

            // Calculate the theoretical range of `D = k - q`.
            // Minimum D occurs when k=0 and q=max_q_for_r: D = -max_q_for_r.
            // Maximum D occurs when k=N and q=0: D = N.
            int min_D = -max_q_for_r; 
            int max_D = N;           
            int D_range_size = max_D - min_D + 1;
            // If the range size is non-positive, skip.
            if (D_range_size <= 0) continue; 
            // Calculate offset to map D values to non-negative indices for vector access.
            int offset = -min_D;

            // `D_deques` stores one deque for each possible value of D.
            // Each deque stores pairs `(q, f(q))`, where `f(q) = dp[k][w] - q * v_i`.
            vector<deque<pair<int, ll>>> D_deques(D_range_size);

            // Iterate through possible quotients `q` from 0 to `max_q_for_r`.
            for (int q = 0; q <= max_q_for_r; ++q) {
                int w = q * weight + r; // Current total weight
                
                // Determine the relevant range of D for the current `q`.
                // Since `k = D + q`, we must have `0 <= k <= N`, which implies `-q <= D <= N - q`.
                // Intersect this with the theoretical range `[min_D, max_D]`.
                int current_min_D = max(min_D, -q);
                int current_max_D = min(max_D, N - q);

                // Iterate through the relevant D values for the current `q`.
                for (int D = current_min_D; D <= current_max_D; ++D) {
                    int k = D + q; // Current number of items

                    // Get the specific deque for the current D value using the offset.
                    deque<pair<int, ll>>& dq = D_deques[D + offset];

                    // Remove elements from the front of the deque whose quotient `q'` is
                    // outside the sliding window `[q - c_i, q]`. The window size corresponds
                    // to using 0 up to `c_i` items of type `i`.
                    while (!dq.empty() && dq.front().first < q - c_i) {
                        dq.pop_front();
                    }
                    
                    // Update `next_dp[k][w]` using the maximum value from the deque.
                    // The maximum `f(q')` value in the window is at the front of the deque.
                    if (!dq.empty()) {
                        ll max_f_q_prime = dq.front().second;
                        // Check if the value is valid (not derived from an initial NINF state).
                        // Use NINF / 2 as a threshold to avoid potential issues near NINF boundary.
                        if (max_f_q_prime > NINF / 2) { 
                            // Calculate the new potential value: `f(q') + q * v_i`
                            ll new_val = max_f_q_prime + (ll)q * v_i;
                            // Update `next_dp[k][w]` if this new value is better.
                            next_dp[k][w] = max(next_dp[k][w], new_val);
                        }
                    }
                    
                    // Consider the value from the DP state *before* processing item `i` (stored in `dp`).
                    // This value `dp[k][w]` represents the max value using items 1 to `i-1`.
                    // It's used to maintain the deque for subsequent `q` values.
                    ll current_dp_val = dp[k][w]; 
                    // Check if the state `(k, w)` was reachable before considering item `i`.
                    if (current_dp_val > NINF / 2) { 
                        // Calculate `f(q) = dp[k][w] - q * v_i`.
                        ll f_q = current_dp_val - (ll)q * v_i;
                        
                        // Maintain the monotonic property of the deque: `f(q)` values should be non-increasing.
                        // Remove elements from the back of the deque that are dominated by the current `f(q)`.
                        while (!dq.empty() && dq.back().second <= f_q) {
                            dq.pop_back();
                        }
                        // Add the current state information `(q, f(q))` to the back of the deque.
                        dq.push_back({q, f_q});
                    }
                }
            }
        }
        // After processing item type `i` for all remainders `r`, update the main DP table `dp`.
        // `std::move` is used for efficiency to transfer ownership of the data.
        dp = std::move(next_dp); 
    }

    // After processing all item types, find and output the answer for each `k` from 1 to N.
    for (int k = 1; k <= N; ++k) {
        ll max_v = NINF; // Initialize max value for k items to NINF.
        // Find the maximum value among all possible weights `w` (0 to N) for fixed `k`.
        for (int w = 0; w <= N; ++w) {
            max_v = max(max_v, dp[k][w]);
        }
        // Output the maximum value found for `k` items.
        // The problem guarantees that a solution exists for each k, so max_v should be updated from NINF.
        cout << max_v << "\n";
    }

    return 0;
}