概要

「今、荷物を何個持っているか」を状態にした動的計画法で解く問題です。
部屋を左から順に見ながら、各荷物数ごとの最大報酬を更新していけば、条件を満たす最大報酬を求められます。

考察

各部屋では仕事を「引き受ける / 断る」を選びますが、制約に関係するのは

• 今までどこまで見たか
• 今、荷物を何個持っているか

の 2 つだけです。

つまり、過去にどの仕事を選んだかの細かい情報は不要で、
「現在の荷物数」だけを状態に持てばよい ことが分かります。

---

1. 素朴な全探索は不可能

各部屋で 2 通りの選択があるので、全探索すると \(2^N\) 通りになります。
\(N \le 10^5\) なので、これはもちろん間に合いません。

---

2. 状態 DP を考える

次のように DP を定義します。

• \(dp[j]\) := 「今まで見た部屋までで、荷物を \(j\) 個持っているような選び方のうち、得られる報酬の最大値」

初期状態では荷物は 0 個なので

• \(dp[0] = 0\)
• \(dp[j] = -\infty \ (j \ge 1)\)

です。

最終的に必要なのは「全部見終わったとき荷物 0 個」なので、答えは最後の \(dp[0]\) です。

---

3. 遷移を考える

荷物を積む仕事 (\(T_i = 1\))

報酬 \(A_i\) を得て、荷物が 1 個増えます。

• 断る: 荷物数は変わらない
• 引き受ける: \(j \to j+1\)（ただし \(j+1 \le K\)）

したがって、遷移は

[ \text{newdp}[j] = \max(\text{newdp}[j], dp[j]) ] [ \text{newdp}[j+1] = \max(\text{newdp}[j+1], dp[j] + A_i) ]

です。

---

荷物を降ろす仕事 (\(T_i = 0\))

報酬 \(A_i\) を得て、

• 荷物が 1 個以上あれば 1 個減る
• 0 個ならそのまま 0 個

です。

つまり、引き受けると

• \(j \ge 1\) なら \(j \to j-1\)
• \(j = 0\) なら \(0 \to 0\)

となります。

よって

[ \text{newdp}[j] = \max(\text{newdp}[j], dp[j]) \quad \text{(断る)} ]

に加えて、

• \(j \ge 1\) については \(dp[j] + A_i\) が \(\text{newdp}[j-1]\) に入る
• \(j = 0\) については \(dp[0] + A_i\) が \(\text{newdp}[0]\) に入る

という形です。

---

4. 「荷物 0 で降ろす仕事」は必ず得

この問題では \(A_i \ge 1\) です。
したがって、荷物 0 個のときに「降ろす仕事」を引き受けても荷物数は変わらず、報酬だけ増えます。

つまり、荷物 0 個でその仕事を断る理由はありません。

この性質のおかげで、降ろす仕事のときの \(j=0\) の遷移は

[

\text{newdp}[0]

\max(dp[0] + A_i,\ dp[1] + A_i) ]

と書けます。
（「断る」は \(dp[0]\) ですが、\(A_i > 0\) なので \(dp[0] + A_i\) のほうが必ず良いです。）

---

5. なぜ 1 次元 DP でよいか

本来は \(i\) 番目の部屋まで見たかどうかも状態に入れると 2 次元 DP になりますが、
各部屋の更新は「1 つ前の状態」しか使わないため、\(i\) の次元は不要です。

よって配列 1 本の 1 次元 DP に圧縮できます。

---

6. そのまま更新すると壊れるので、更新順に注意

1 次元でその場更新する場合、同じ部屋を複数回使ったことにならないように更新順を工夫する必要があります。

• 積む仕事: \(j \to j+1\) へ遷移するので、大きい \(j\) から小さい \(j\) へ 更新する
• 降ろす仕事: \(j+1 \to j\) へ遷移するので、小さい \(j\) から大きい \(j\) へ 更新する

これで、各部屋の仕事をちょうど 1 回だけ使った正しい遷移になります。

アルゴリズム

DP 配列 \(dp[0 \ldots K]\) を用いる。

• 初期化:
  • \(dp[0] = 0\)
  • それ以外は \(-\infty\)

各部屋 \((T_i, A_i)\) について以下を行う。

1. \(T_i = 1\)（積む仕事）

荷物数が 1 増えるので、後ろから更新する。

[ dp[j+1] = \max(dp[j+1], dp[j] + A_i) \quad (j = K-1, K-2, \dots, 0) ]

「断る」場合は \(dp[j]\) をそのまま残せばよい。

---

2. \(T_i = 0\)（降ろす仕事）

荷物数が 1 減る（0 のときは 0 のまま）ので、前から更新する。

まず \(dp[0]\) は古い \(dp[0], dp[1]\) の両方から来るので先に計算しておく。

[ best0 = \max(dp[0] + A_i,\ dp[1] + A_i) ]

次に \(j = 1\) から \(K-1\) について

[ dp[j] = \max(dp[j], dp[j+1] + A_i) ]

と更新する。

最後に

[ dp[0] = best0 ]

とする。
\(dp[K]\) は「断る」場合しか残れないのでそのままでよい。

---

すべての部屋を処理した後の

[ dp[0] ]

が答えです。

計算量

• 時間計算量: \(O(NK)\)
• 空間計算量: \(O(K)\)

制約に \(NK \le 10^7\) があるので、この計算量で十分間に合います。

実装のポイント

• 到達不可能な状態は十分小さい値（例えば -10**30）で初期化する
• 積む仕事は後ろから更新
• 降ろす仕事は前から更新
• 降ろす仕事のときの dp[0] は、dp[1] を上書きする前に別変数 best0 に保存しておく

この 3 点を守れば、コードを安全に 1 次元 DP で実装できます。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    it = iter(data)
    N = next(it)
    K = next(it)

    NEG = -10**30
    dp = [NEG] * (K + 1)
    dp[0] = 0

    for _ in range(N):
        t = next(it)
        a = next(it)

        if t == 1:
            for j in range(K - 1, -1, -1):
                v = dp[j] + a
                if v > dp[j + 1]:
                    dp[j + 1] = v
        else:
            best0 = dp[0] + a
            v = dp[1] + a
            if v > best0:
                best0 = v
            for j in range(1, K):
                v = dp[j + 1] + a
                if v > dp[j]:
                    dp[j] = v
            dp[0] = best0

    print(dp[0])

if __name__ == "__main__":
    main()

---

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