概要

到着時刻 \(S\) から閉店時刻 \(T\) までの残り時間 \(T-S\) の中で、いくつかの商品を（各商品は高々1回）選んで購入し、得られるお得さの合計を最大化する問題です。

考察

• 高橋君が実際に使える時間は、開始時刻 \(0\) からではなく到着時刻 \(S\) からなので、使える総時間は \(L = T - S\) 分です。問題は「時間制限 \(L\) の中で、各商品（時間 \(C_i\)・価値 \(P_i\)）を選んで価値合計を最大化する」に言い換えられます。
• これは典型的な 0/1 ナップサック問題（各品物を選ぶか選ばないか）です。
  
  • 「同時に複数の手続きはできない」「途中でやめられない」→ 購入する商品は順に処理する必要があり、各商品の所要時間はそのまま“重さ”になります。
  • 「閉店までに完了しないとダメ」→ 合計時間が \(L\) を超える選び方は不可です。
• 素朴に「全ての商品の購入/非購入を試す」と \(2^N\) 通りで、\(N \le 100\) では到底間に合いません（TLE）。
• そこで、時間を軸にした動的計画法（DP）で「この時間以内で得られる最大価値」を更新していけば、\(N \le 100, \; L \le 10^4\) なら十分高速に解けます。

（例）\(L=5\)、商品が \((C,P)=(2,4),(3,5)\) のとき
- 時間5以内で選べる組み合わせは「どちらか片方」または「両方（2+3=5）」で、最大は \(4+5=9\)。
DPはこのような最適値を機械的に計算します。

アルゴリズム

0/1 ナップサックDPを用います。

• 残り時間 \(L = T - S\) を計算する。
• \(dp[t] =\)「合計時間が \(t\) 以下 で達成できるお得さの最大値」とする（実装上は添字 \(t\) を“時間上限”として持つ）。
• 各商品 \((c,p)\) について、次を行う：
  • もし \(c > L\) なら、そもそも残り時間内に買えないので無視する。
  • \(t\) を \(L\) から \(c\) まで 降順に走査して更新する：
    • その商品を買う場合、\(dp[t-c] + p\)
    • 買わない場合、\(dp[t]\)
    • より大きい方を採用：\(dp[t] = \max(dp[t], dp[t-c] + p)\)
• 最後に答えは \(\max(dp)\)（時間を使い切らない最適解もあるため）。

降順ループが重要です。昇順にすると、同じ商品を同一周回内で何度も使った状態（無制限ナップサック）になってしまい、誤答（WA）になります。

計算量

• 時間計算量: \(O(NL)\)（\(L = T-S \le 10^4\)）
• 空間計算量: \(O(L)\)

実装のポイント

• 使える時間は \(T\) ではなく \(L = T-S\) に置き換える。

• 0/1ナップサックなので、\(t\) のループは必ず 大きい方から小さい方へ（降順） 回す。

• \(c > L\) の商品は事前にスキップすると無駄な更新が減る。

• 最終的に時間を使い切る必要はないため、print(max(dp)) のように最大値を取るのが安全です。

  ソースコード

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()

この解説は gpt-5.2-high によって生成されました。