Overview

Plants with drought resistance \(B_i \ge T\) (at or above the threshold \(T\)) survive even without watering, so their value is unconditionally added. The problem reduces to finding the maximum value of “wilting plants” (\(B_i < T\)) that can be saved within budget \(M\).

Analysis

There are two key observations:

1. Some plants don’t wilt even without watering
   Plants with drought resistance \(B_i \ge T\) do not wilt even without watering facilities.
   Therefore, they “always survive,” so their aesthetic value \(A_i\) can be added to the total from the start (base in the code).

2. Wilting plants have a binary choice: save or discard
   Plants with \(B_i < T\) will inevitably wilt unless watered.
   Thus, for each plant in this group, we choose one of the following:

   • Save it (pay cost \(C_i\) to gain value \(A_i\))
   • Discard it (pay nothing, gain value \(0\))

After this simplification, the problem becomes a 0/1 knapsack problem considering only the “wilting plants.”

• Capacity (budget): \(M\)
• Items (wilting plants): each with “weight \(C_i\)” and “value \(A_i\)”
• Objective: maximize total value

A brute-force approach trying all subsets of plants would require \(2^N\) combinations, which is far too slow for \(N \le 100\). Greedy approaches such as “select in order of highest value/cost ratio” also cannot guarantee an optimal solution for the 0/1 knapsack in general.

Algorithm

1. Divide the plants into two categories:
   • Plants with \(B_i \ge T\): they always survive, so base += A_i
   • Plants with \(B_i < T\): add them as knapsack items (cost=C_i, value=A_i) to an array
2. Perform 0/1 knapsack DP:
   • Let dp[m] be “the maximum value of wilting plants that can be saved within budget \(m\)”
   • Initialize dp[0..M] = 0
   • For each item (cost, value), update the budget from largest to smallest (to prevent using the same item multiple times): $\( dp[m] = \max(dp[m],\ dp[m-cost] + value) \quad (m = M, M-1, \dots, cost) \)$
3. The final answer is $\( \text{base} + \max_{0 \le m \le M} dp[m] \)$ (Since we don’t need to exhaust the entire budget, we take max(dp))

Complexity

• Time complexity: \(O(NM)\) (at most around \(100 \times 10^4 = 10^6\))
• Space complexity: \(O(M)\) (one-dimensional DP array)

Implementation Notes

• The one-dimensional DP update must iterate in reverse order (\(m = M \to cost\)). If you iterate forward, the same plant can be selected multiple times, turning it into an “unbounded knapsack” and producing incorrect results.

• Plants with cost > M can never be saved within the budget, so they can be skipped (if cost > M: continue in the code).

• At the end, since leftover budget is allowed, use max(dp) instead of dp[M].

  Source Code

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()

This editorial was generated by gpt-5.2-high.