概要

乾燥耐性 \(B_i\) が閾値 \(T\) 以上の植物は放置しても生き残るので、その価値は確定で加算し、\(B_i<T\) の「枯れる植物」だけを予算 \(M\) の範囲で救う最大価値を求める問題です。

考察

重要な観察は次の2点です。

1. 給水しなくても枯れない植物がある
   乾燥耐性が \(B_i \ge T\) の植物は、給水設備がなくても枯れません。
   よってこれらは「必ず残る」ので、観賞価値 \(A_i\) は最初から合計に入れてよい（コード中の base）。

2. 枯れる植物は「救うか捨てるか」の二択
   \(B_i < T\) の植物は、給水しない限り必ず枯れます。
   したがってこのグループについては、各植物を

   • 救う（コスト \(C_i\) を払って価値 \(A_i\) を得る）
   • 捨てる（何も払わず価値 \(0\)） のどちらかを選ぶことになります。

ここまで整理すると、「枯れる植物」だけを対象にした 0/1 ナップサック問題になります。

• 容量（予算）: \(M\)
• 品物（枯れる植物）: それぞれ「重さ \(C_i\)」「価値 \(A_i\)」
• 目的: 価値の合計最大化

素朴に「どの植物に給水するか」を全探索すると \(2^N\) 通りになり、\(N \le 100\) では到底間に合いません。また「価値/コストが高い順に選ぶ」などの貪欲法も、0/1 ナップサックでは一般に最適解を保証できません。

アルゴリズム

1. 植物を2種類に分ける：
   • \(B_i \ge T\) の植物：必ず生き残るので base += A_i
   • \(B_i < T\) の植物：ナップサックの品物として (cost=C_i, value=A_i) を配列に入れる
2. 0/1 ナップサックDPを行う：
   • dp[m] を「予算 \(m\) 以内で救える枯れる植物の価値の最大値」とする
   • 初期値 dp[0..M] = 0
   • 各品物 (cost, value) について、予算を 大きい方から更新する（同じ品物を複数回使わないため）
     $\( dp[m] = \max(dp[m],\ dp[m-cost] + value) \quad (m = M, M-1, \dots, cost) \)$
3. 最終的な答えは $\( \text{base} + \max_{0 \le m \le M} dp[m] \)$ （予算を使い切る必要はないため max(dp) を取る）

計算量

• 時間計算量: \(O(NM)\)（最大でも \(100 \times 10^4 = 10^6\) 程度）
• 空間計算量: \(O(M)\)（一次元DP配列）

実装のポイント

• 一次元DPの更新は必ず逆順（\(m=M \to cost\)）に回します。順方向にすると同じ植物を何回も選べる「無制限ナップサック」になってしまい誤答になります。

• cost > M の植物は、どう頑張っても予算内で救えないのでスキップしてよいです（コードの if cost > M: continue）。

• 最後は「予算を余らせてもよい」ので dp[M] ではなく max(dp) を使います。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M, T = map(int, input().split())
    base = 0
    vulnerable = []
    for _ in range(N):
        A, B, C = map(int, input().split())
        if B >= T:
            base += A
        else:
            vulnerable.append((C, A))

    dp = [0] * (M + 1)
    for cost, val in vulnerable:
        if cost > M:
            continue
        for m in range(M, cost - 1, -1):
            nv = dp[m - cost] + val
            if nv > dp[m]:
                dp[m] = nv

    print(base + max(dp))

if __name__ == "__main__":
    main()

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