Overview

This is a problem where, within the remaining time \(T-S\) from arrival time \(S\) to closing time \(T\), you select some items to purchase (each item at most once) and maximize the total savings obtained.

Analysis

• Since Takahashi can only use time starting from arrival time \(S\) rather than time \(0\), the total available time is \(L = T - S\) minutes. The problem can be rephrased as: “Within a time limit of \(L\), select items (each with time \(C_i\) and value \(P_i\)) to maximize the total value.”
• This is a classic 0/1 knapsack problem (choose or not choose each item).
  • “Cannot process multiple procedures simultaneously” and “Cannot stop midway” → Items to purchase must be processed sequentially, and each item’s required time directly becomes its “weight.”
  • “Must complete before closing” → Selections where the total time exceeds \(L\) are not allowed.
• A naive approach of “trying all purchase/non-purchase combinations” yields \(2^N\) possibilities, which is far too slow for \(N \le 100\) (TLE).
• Instead, by using dynamic programming (DP) along the time axis to update “the maximum value achievable within this amount of time,” we can solve it efficiently enough for \(N \le 100, \; L \le 10^4\).

(Example) When \(L=5\) and items are \((C,P)=(2,4),(3,5)\): - Combinations selectable within time 5 are “either one” or “both (2+3=5),” and the maximum is \(4+5=9\). DP mechanically computes such optimal values.

Algorithm

We use 0/1 Knapsack DP.

• Compute the remaining time \(L = T - S\).
• Let \(dp[t] =\) “the maximum savings achievable with total time at most \(t\)” (in implementation, index \(t\) is held as the “time limit”).
• For each item \((c, p)\), do the following:
  • If \(c > L\), it cannot be purchased within the remaining time, so skip it.
  • Iterate \(t\) from \(L\) down to \(c\) in descending order and update:
    • If we buy this item: \(dp[t-c] + p\)
    • If we don’t buy it: \(dp[t]\)
    • Take the larger value: \(dp[t] = \max(dp[t], dp[t-c] + p)\)
• The final answer is \(\max(dp)\) (since the optimal solution may not use all the available time).

The descending loop is crucial. If you iterate in ascending order, the same item can be used multiple times within the same pass (unbounded knapsack), leading to wrong answers (WA).

Complexity

• Time complexity: \(O(NL)\) (\(L = T-S \le 10^4\))
• Space complexity: \(O(L)\)

Implementation Notes

• Replace the available time with \(L = T-S\), not \(T\).

• Since this is a 0/1 knapsack, the loop over \(t\) must always go from large to small (descending order).

• Items with \(c > L\) can be skipped beforehand to avoid unnecessary updates.

• Since there is no need to use up all the time, it is safe to take the maximum value as print(max(dp)).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, T, S = map(int, input().split())
    L = T - S  # remaining time
    dp = [0] * (L + 1)

    for _ in range(N):
        c, p = map(int, input().split())
        if c > L:
            continue
        for t in range(L, c - 1, -1):
            val = dp[t - c] + p
            if val > dp[t]:
                dp[t] = val

    print(max(dp))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.