Overview

This problem asks us to find the maximum total satisfaction when selecting from \(N\) types of products (each with weight \(w_i\), satisfaction \(v_i\), and stock \(c_i\)) such that the total weight is exactly \(S\). This reduces to the classic “Bounded Knapsack Problem”.

Analysis

Naive Approach and Its Limitations

Consider a dynamic programming (DP) approach where, for each product \(i\), we exhaustively try all possible quantities \(k\) from \(0\) to \(c_i\). Define \(dp[i][j]\) as “the maximum satisfaction achievable using products up to the \(i\)-th one with a total weight of exactly \(j\).” The transition is as follows:

\[dp[i][j] = \max_{0 \le k \le c_i} (dp[i-1][j - k \cdot w_i] + k \cdot v_i)\]

Here, the number of states is \(O(NS)\), and each state transition takes \(O(c_i)\), so the overall time complexity is \(O(S \sum c_i)\). Looking at the constraints: \(N \le 100\), \(S \le 30000\), \(c_i \le 10^5\). In the worst case, this requires approximately \(100 \times 30000 \times 10^5 = 3 \times 10^{11}\) operations, which is far too slow to meet the time limit (resulting in TLE).

Optimization via Binary (Power of 2) Splitting

A powerful technique for efficiently solving the bounded knapsack problem is “binary splitting (power-of-2 decomposition)”.

For example, suppose a product can be selected “up to 13 times.” Instead of considering one item at a time, we split the product into the following groups and convert each into a “use or don’t use” binary choice (0-1 knapsack problem): - A group of \(1\) item - A group of \(2\) items - A group of \(4\) items - A group of \(6\) items (the remaining \(13 - (1 + 2 + 4) = 6\) items)

By combining some subset of these groups \(\{1, 2, 4, 6\}\) (deciding whether to select each group or not), we can represent any quantity from \(0\) to \(13\) without excess or shortage (e.g., to select \(5\) items, choose the groups of \(1\) and \(4\); to select \(11\) items, choose the groups of \(1\), \(4\), and \(6\)).

In general, a quantity \(c\) can be decomposed into \(O(\log c)\) groups. This allows us to transform the bounded knapsack problem into a “0-1 knapsack problem” with \(O(N \log c)\) items.

Algorithm

1. DP Table Initialization: Prepare a DP array dp of size \(S + 1\), initialized entirely to -1 (representing unreachable states). Since the satisfaction at weight \(0\) is \(0\), set dp[0] = 0.
2. Reducing the Quantity: For each product, since its weight is \(w_i\), it is impossible to buy more than \(\lfloor S / w_i \rfloor\) items regardless. Therefore, by setting \(c_i = \min(c_i, \lfloor S / w_i \rfloor)\) in advance, we can avoid unnecessary decomposition.
3. Binary Splitting and DP Update: For each product \(i\), decompose the remaining stock \(c_i\) into groups of sizes \(1, 2, 4, 8, \dots\) (powers of 2). For each decomposed virtual item with “weight \(cur\_w = w_i \times mul\) and satisfaction \(cur\_v = v_i \times mul\),” update the DP table from back to front, just like in a standard 0-1 knapsack problem: $\(dp[j] = \max(dp[j], dp[j - cur\_w] + cur\_v)\)\( (The transition is only performed when the source `dp[j - cur_w]` holds a valid value (\)\neq -1$).)
4. Output the Answer: Output the value stored in dp[S]. If the value remains -1, it is impossible to achieve exactly weight \(S\), so output -1.

Complexity

• Time Complexity: \(O(S \sum_{i=1}^N \log(\min(c_i, S/w_i)))\) The stock \(c_i\) of each product is decomposed into at most \(O(\log c_i)\) groups. Since the effective maximum quantity is bounded by \(S/w_i\), the total number of items after decomposition is at most around \(N \log S\). The DP transition takes \(O(S)\) per item, which is well within the time limit (in the worst case, approximately \(100 \times 15 \times 30000 \approx 4.5 \times 10^7\) loop iterations, which runs in tens of milliseconds in C++).
• Space Complexity: \(O(S)\) Since we reuse the DP table as a 1-dimensional array (in-place update), the required memory is only proportional to the target weight \(S\), making it very lightweight.

Implementation Notes

• DP Update Order: When performing 0-1 knapsack DP with a 1-dimensional array, to avoid selecting the same item multiple times, the loop over weight \(j\) must iterate in reverse order (descending) from \(S\) down to \(cur\_w\).

• Overflow Caution: The maximum satisfaction can reach up to \(N \times \max(c_i) \times \max(v_i) \approx 100 \times 10^5 \times 10^4 = 10^{11}\). This exceeds the maximum value of a standard 32-bit integer (int, approximately \(2 \times 10^9\)), so the DP array storing satisfaction values and related computation variables must use a 64-bit integer type (long long in C++).

  Source Code

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

using namespace std;

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, S;
    if (!(cin >> N >> S)) return 0;

    // dp[j] : 重さの合計がちょうど j のときの満足度の最大値。不可能な場合は -1
    vector<long long> dp(S + 1, -1);
    dp[0] = 0;

    for (int i = 0; i < N; ++i) {
        long long w, v, c;
        cin >> w >> v >> c;

        // 重さの合計が S を超える分は購入する必要がないため、個数を制限する
        c = min(c, (long long)S / w);
        if (c <= 0) continue;

        // 個数制限付きナップサック問題を 01 ナップサック問題に変換（2の冪乗分割）
        long long k = 1;
        while (c > 0) {
            long long mul = min(k, c);
            long long cur_w = w * mul;
            long long cur_v = v * mul;

            for (int j = S; j >= cur_w; --j) {
                if (dp[j - cur_w] != -1) {
                    dp[j] = max(dp[j], dp[j - cur_w] + cur_v);
                }
            }
            c -= mul;
            k *= 2;
        }
    }

    cout << dp[S] << "\n";

    return 0;
}

This editorial was generated by gemini-3.5-flash-thinking.