Overview

This problem asks us to maximize the total aesthetic value of plants that survive without wilting, within a budget of \(M\). The key observation is that plants fall into two categories: “those that survive unconditionally” and “those that wilt unless a watering system is installed.” By solving the latter as a 0/1 knapsack problem, we can arrive at the correct answer.

Analysis

First, let’s organize the conditions under which each plant survives.

1. Plants with drought tolerance \(B_i \ge T\) These do not wilt even without a watering system. Therefore, we can obtain their aesthetic value \(A_i\) without spending any budget.
2. Plants with drought tolerance \(B_i < T\) These survive if a watering system is installed (at cost \(C_i\)), but wilt otherwise.

From this, the problem can be decomposed into two steps:

• Step 1: Sum up the aesthetic values \(A_i\) of all plants with \(B_i \ge T\) (call this base_appreciation).
• Step 2: From the plants with \(B_i < T\), select some such that the total cost does not exceed \(M\), and maximize the total aesthetic value \(A_i\) of the selected plants.

Step 2 is exactly a classic 0/1 knapsack problem: “maximize the total value while keeping the total weight (cost) within a limit.”

Algorithm

1. Classification

Scan each plant. If \(B_i \ge T\), add its value to the running total. If \(B_i < T\), add it to the list of knapsack item candidates (value \(A_i\), cost \(C_i\)).

2. Dynamic Programming (DP)

To solve the knapsack problem, define the following DP table: dp[j]: the maximum total aesthetic value obtainable using budget \(j\)

The initial state is dp[0...M] = 0. For each item \((A_i, C_i)\), update the DP table: $\(dp[j] = \max(dp[j], dp[j - C_i] + A_i)\)\( ※ The key point is to update the budget \)j\( in **reverse order** from \)M\( down to \)C_i$, to prevent selecting the same item more than once.

The final answer is base_appreciation + dp[M].

Complexity

• Time complexity: \(O(NM)\)
  • Classifying the plants takes \(O(N)\), and updating the DP takes \(O(N \times M)\).
  • Given the constraints \(N \le 100, M \le 10^4\), the maximum number of operations is around \(10^6\), which runs sufficiently fast.
• Space complexity: \(O(M)\)
  • Memory is needed to maintain a DP table of size \(M\).

Implementation Notes

• Reverse loop: When updating a 1-dimensional DP table for the 0/1 knapsack problem, iterating the inner loop (over the budget) from the larger values downward prevents the duplication of selecting the same plant twice.

• Large threshold values: Although \(T\) and \(B_i\) can be as large as \(10^9\), they are only used for comparison, so they do not affect the DP computation complexity.

  Source Code

import sys

def solve():
    # 入力を標準入力からすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 1行目の N (植物の種類数), M (予算), T (乾燥耐性の閾値) を取得
    N = int(input_data[0])
    M = int(input_data[1])
    T = int(input_data[2])
    
    base_appreciation = 0
    vulnerable_items = []
    
    # 各植物の情報を読み込む
    # A: 観賞価値, B: 乾燥耐性, C: 給水設備の設置コスト
    for i in range(N):
        a = int(input_data[3 + i * 3])
        b = int(input_data[3 + i * 3 + 1])
        c = int(input_data[3 + i * 3 + 2])
        
        if b >= T:
            # 乾燥耐性が閾値 T 以上であれば、給水設備がなくても枯れない
            base_appreciation += a
        else:
            # 乾燥耐性が T 未満であれば、給水設備を設置した場合のみ枯れずに残る
            vulnerable_items.append((a, c))
            
    # dp[j] は、予算 j 以内で給水設備を設置して得られる観賞価値の最大合計 (0/1 ナップサック問題)
    dp = [0] * (M + 1)
    
    for a, c in vulnerable_items:
        # コスト c の植物を設置するか検討
        # 重複して選ばないように後ろから更新する
        for j in range(M, c - 1, -1):
            if dp[j - c] + a > dp[j]:
                dp[j] = dp[j - c] + a
                
    # もともと枯れない植物の価値と、予算内で救った植物の価値の合計を出力
    print(base_appreciation + dp[M])

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-preview.