Overview

This is a problem of selecting from \(N\) products such that the total price is exactly \(S\) yen, and finding the maximum total satisfaction.

Analysis

Exhaustively searching all ways to select products results in \(2^N\) possibilities, which will not finish within the time limit (TLE) given the constraint \(N \leq 3000\). This problem is a variation of the well-known “knapsack problem” and can be solved efficiently using dynamic programming (DP).

The standard knapsack problem finds the maximum value under the condition “the total cost (weight) is at most \(S\)”, but in this problem the condition is “the total cost is exactly \(S\) yen”. Therefore, we need to compute the maximum while distinguishing whether a selection that achieves exactly that amount exists or not.

Algorithm

We solve this using dynamic programming (DP) with a one-dimensional array.

Define dp[j] as “the maximum total satisfaction when the total price is exactly \(j\) yen.”

1. Initialization In the initial state where no products have been considered yet, the satisfaction when the total price is \(0\) yen is \(0\). All other amounts are unreachable, so we initialize them with -1 to indicate they are not achievable. - dp[0] = 0 - dp[j] = -1 \((1 \leq j \leq S)\)

2. Transition (DP Update) For each product (satisfaction \(V_i\), price \(C_i\)), iterate over the amount \(j\) from large to small and update as follows: - If dp[j - C_i] is not -1 (i.e., a way to achieve a total price of \(j - C_i\) yen already exists), then - Update the maximum as dp[j] = max(dp[j], dp[j - C_i] + V_i).

3. Output the Answer After processing all products, dp[S] is the desired answer. If dp[S] remains -1, it means there is no way to select products totaling exactly \(S\) yen, so output -1 as is.

Complexity

• Time complexity: \(O(NS)\) The number of loop iterations is proportional to the product of the number of products \(N\) and the target amount \(S\). At most, this is about \(3000 \times 10000 = 3 \times 10^7\) operations, which is well within the time limit.
• Space complexity: \(O(S)\) We only need a single one-dimensional array of length \(S+1\), so memory usage is kept very low.

Implementation Notes

• Update order with a one-dimensional array: When using a one-dimensional array for state updates, the inner loop must always iterate from large amounts to small amounts (in reverse order). If you iterate from small to large, the same product may be purchased multiple times, leading to incorrect results.

• Constant factor optimization: In the solution code, a variable max_w is used to track “the maximum achievable amount so far.” This allows us to limit the starting position of the inner loop to min(S, max_w + c) instead of always starting from \(S\), reducing unnecessary iterations and further improving execution speed.

  Source Code

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    S = int(data[1])
    
    dp = [-1] * (S + 1)
    dp[0] = 0
    
    max_w = 0
    idx = 2
    for _ in range(N):
        v = int(data[idx])
        c = int(data[idx+1])
        idx += 2
        
        limit = S if max_w + c > S else max_w + c
        for j in range(limit, c - 1, -1):
            prev = dp[j - c]
            if prev != -1:
                cand = prev + v
                if dp[j] < cand:
                    dp[j] = cand
        if max_w < limit:
            max_w = limit
            
    print(dp[S])

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.