Overview

Given a remaining time of \(T - S\) minutes, the problem asks you to select items to purchase and maximize the total savings. This can be reduced to the classic 0-1 Knapsack Problem.

Analysis

Takahashi arrives at the department store at time \(S\) and the store closes at time \(T\), so the available shopping time is \(W = T - S\) minutes.

Each item has a “processing time \(C_i\)” and an “obtained savings \(P_i\)”, and only items whose processing completes within the time limit \(W\) can be purchased. The same item cannot be bought twice.

This can be rephrased as follows:

Given a knapsack of capacity \(W\), pack items with weight \(C_i\) and value \(P_i\) to maximize the total value.

For example, with \(N=3, T=10, S=4\) (remaining time \(W=6\)) and the following items:

Item	Time \(C_i\)	Savings \(P_i\)
1	3	50
2	4	60
3	2	30

Buying item 1 (3 minutes) and item 3 (2 minutes) fits within 5 minutes total, yielding savings of \(50 + 30 = 80\) yen. Buying items 1 and 2 gives \(3+4=7 > 6\), which exceeds the time limit.

Naively trying all combinations of items requires \(2^N\) possibilities, which is far too slow when \(N=100\). Therefore, we use Dynamic Programming (DP).

Algorithm

We solve the 0-1 Knapsack Problem using a 1-dimensional DP.

• \(dp[j]\) = the maximum savings obtainable using at most \(j\) minutes of remaining time
• Initial values: \(dp[j] = 0\) (the state where nothing is bought)

For each item \((C_i, P_i)\), iterate \(j\) from \(W\) down to \(C_i\) in reverse order, applying the following transition:

\[dp[j] = \max(dp[j],\ dp[j - C_i] + P_i)\]

The reason for iterating in reverse order is to prevent selecting the same item more than once. If we iterated in ascending order, the result of selecting an item could be reused within the same loop, potentially selecting the same item multiple times.

The final answer is \(dp[W]\).

Complexity

• Time complexity: \(O(N \times W)\) (\(W = T - S\))
  • Since \(N \leq 100\) and \(W \leq 10^4\), the maximum number of operations is \(100 \times 10^4 = 10^6\), which is sufficiently fast.
• Space complexity: \(O(W)\)
  • Only a 1-dimensional array is used.

Implementation Notes

• Calculating remaining time: Compute \(W = T - S\) from the arrival time \(S\) and closing time \(T\) at the beginning. When \(S = T\), we have \(W = 0\), meaning nothing can be bought, so the answer is \(0\).

• Reverse loop: for j in range(W, c - 1, -1) guarantees that each item is selected at most once. This is a standard technique for the 0-1 knapsack problem.

• Using 1-dimensional DP: While a 2-dimensional array \(dp[i][j]\) (considering the first \(i\) items with capacity \(j\)) is also possible, a 1-dimensional array is sufficient and more memory-efficient.

  Source Code

N, T, S = map(int, input().split())
W = T - S
items = []
for _ in range(N):
    c, p = map(int, input().split())
    items.append((c, p))

# 0-1 knapsack
dp = [0] * (W + 1)
for c, p in items:
    for j in range(W, c - 1, -1):
        dp[j] = max(dp[j], dp[j - c] + p)

print(dp[W])

---

This editorial was generated by claude4.6opus-thinking.