概要

予算の制限がある中で、植物に給水設備を設置して枯らさないことで、残る植物の観賞価値の合計を最大化する問題です。

考察

この問題では、各植物に「観賞価値 \(A_i\)」「乾燥耐性 \(B_i\)」「給水コスト \(C_i\)」が与えられています。
まず重要な観察として、「乾燥耐性 \(B_i \geq T\)」の植物は自然に枯れないため、必ず観賞価値を得ることができます。したがって、これらの植物の観賞価値は合計にそのまま加算されます。

一方で、「乾燥耐性 \(B_i < T\)」の植物は、給水設備を設置しないと確実に枯れてしまいます。このような植物に対してだけ、予算内で観賞価値を最大化するように給水設備を選ぶ必要があります。

つまり、問題は次のように言い換えられます：

「予算 \(M\) 以内で、\(B_i < T\) である植物の中からいくつか選び、それらに給水設備を設置する。その結果、残った植物（枯れない植物）の観賞価値の合計を最大化せよ」

これは典型的な「ナップサック問題」と見なせます。各植物は「コスト \(C_i\)」を持っており、選ぶことで「価値 \(A_i\)」を得ることができ、制約は「コストの合計が \(M\) 以下」です。

素朴な全探索では、\(N\) が最大100なので、\(2^{100}\) 通りとなり現実的ではありません（TLE）。しかし、ナップサック問題は動的計画法（DP）によって効率的に解くことができます。

アルゴリズム

1. 植物を2つのグループに分ける：

   • 枯れない植物：\(B_i \geq T\) のもの → 合計観賞価値に加える
   • 枯れる可能性のある植物：\(B_i < T\) のもの → ナップサック問題として扱う

2. 枯れる可能性のある植物について、0-1ナップサック問題を解く：

   • dp[w] := 予算 \(w\) 以内で得られる最大の観賞価値
   • 各植物 \((A_i, C_i)\) に対して、DPテーブルを更新：
     • 更新式：dp[w] = max(dp[w], dp[w - C_i] + A_i) （\(w \geq C_i\) の範囲で逆順に更新）

3. 最終的な答えは： $\( \text{安全な植物の観賞価値の合計} + \max_{0 \leq w \leq M} dp[w] \)$

計算量

• 時間計算量: \(O(N \cdot M)\)
• 空間計算量: \(O(M)\)

実装のポイント

• DPテーブルを1次元で持つことで空間計算量を削減できる
• 物品を追加する際に、予算の大きい方から小さい方へ逆順に更新しないと、同じ物品を複数回選んでしまうので注意
• 入力を高速に読み込むために sys.stdin.read を使用している（特にPythonでTLEしないための工夫）

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    T = int(data[idx])
    idx += 1
    
    plants = []
    for _ in range(N):
        A = int(data[idx])
        idx += 1
        B = int(data[idx])
        idx += 1
        C = int(data[idx])
        idx += 1
        plants.append((A, B, C))
    
    # 枯れる可能性のある植物（B_i < T）のみを抽出
    vulnerable = [(A, C) for A, B, C in plants if B < T]
    # 枯れない植物（B_i >= T）の観賞価値の合計
    safe_value = sum(A for A, B, C in plants if B >= T)
    
    # ナップサック問題を解く
    # dp[i][w] := i番目まで見て予算w以下で得られる最大の観賞価値
    num_vul = len(vulnerable)
    if num_vul == 0:
        print(safe_value)
        return
    
    # DPテーブル初期化
    dp = [0] * (M + 1)
    
    for A, C in vulnerable:
        # 逆順に更新しないと重複して選択してしまう
        for w in range(M, C - 1, -1):
            dp[w] = max(dp[w], dp[w - C] + A)
    
    # 最大値を取得
    max_dp = max(dp)
    result = safe_value + max_dp
    print(result)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。