概要

残り時間 \(M\) 分以内でいくつかの宿題（各1回まで）を選び、完成度ポイント合計を最大化する問題です。典型的な 0/1ナップサック問題として動的計画法で解きます。

考察

• 各宿題は「やる / やらない」の2択で、同じ宿題は複数回できません。したがって「時間 \(M\) を超えない範囲で価値（完成度）を最大化する」= 0/1ナップサックの形になります。
• 素朴に全探索すると、宿題の選び方は \(2^N\) 通りあります。\(N \le 100\) なので \(2^{100}\) は到底計算できず TLE になります。
• また、例えば「完成度が高い順」や「完成度/時間が高い順」のような貪欲法は一般には正しくありません。
  例：\(M=10\)、(R,T) = (10,6), (9,5), (9,5) のとき
  貪欲に (10,6) を選ぶと残り4分で他は選べず合計10点。
  しかし (9,5)+(9,5)=18点 が最適です。
• そこで「時間をどれだけ使ったか」を状態にして、宿題を順に見ながら最適値を更新する DP を使います。

アルゴリズム

DP配列の定義
- \(dp[w]\) := 「合計時間をちょうど \(w\) 分使うときの、得られる完成度ポイントの最大値」 - 到達不可能な状態は非常に小さい値（\(-\infty\)）で初期化します。 - 初期状態は「何もやらず時間0」なので \(dp[0]=0\)、それ以外は \(-\infty\)。

遷移（宿題 \((R_i, T_i)\) を処理） - この宿題を選ぶなら、以前に時間 \((w-T_i)\) を達成していて、そこに \(T_i\) 分と \(R_i\) 点を足す： $\( dp[w] = \max(dp[w],\ dp[w-T_i] + R_i) \)\( - ただし、同じ宿題を複数回使わない（0/1）ために、\)w\( は **大きい方から小さい方へ**（\)M \to T_i\(）走査します。 小さい方から更新すると、更新済みの \)dp$ を同じ宿題で再利用してしまい「無限回選べる」状態（別問題）になってしまいます。

答え - 条件は「合計時間が \(M\) 以下」なので、ちょうど \(M\) とは限りません。よって $\( \max_{0 \le w \le M} dp[w] \)$ を出力します（コードでは max(dp)）。

計算量

• 時間計算量: \(O(NM)\)
  （各宿題ごとに \(w=0..M\) 相当を1回更新）
• 空間計算量: \(O(M)\)
  （1次元DP配列のみ）

実装のポイント

• 到達不可能を表すために NEG = -10**30 のような十分小さい値を使い、dp[w-t] != NEG のときだけ遷移します（不正な加算を防ぐ）。

• 更新順は必ず降順（for w in range(M, t-1, -1):）。これが 0/1 ナップサックの要点です。

• 完成度 \(R_i\) は最大 \(10^9\)、合計はさらに大きくなりうるため、Python の int（任意精度）で安全に扱えます。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())
    NEG = -10**30
    dp = [NEG] * (M + 1)
    dp[0] = 0

    for _ in range(N):
        r, t = map(int, input().split())
        for w in range(M, t - 1, -1):
            prev = dp[w - t]
            if prev != NEG:
                val = prev + r
                if val > dp[w]:
                    dp[w] = val

    print(max(dp))

if __name__ == "__main__":
    main()

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