Overview

This problem involves solving a 0-1 knapsack problem where plants with drought tolerance at or above the threshold automatically survive, and for plants below the threshold, we install irrigation equipment within the budget.

Analysis

Key Insight

Plants can be divided into two groups based on the relationship between their drought tolerance \(B_i\) and the threshold \(T\):

1. Safe plants (\(B_i \geq T\)): They don’t wither even without irrigation equipment → They always survive
2. Vulnerable plants (\(B_i < T\)): They wither without irrigation equipment → They survive only if equipment is installed

Safe plants survive without any action, so their ornamental value is obtained unconditionally.

For vulnerable plants, this becomes a selection problem: “Which plants should we install irrigation equipment for, within budget \(M\), to maximize the total ornamental value?”

Problem with the Naive Approach

When there are \(K\) vulnerable plants, trying all combinations results in \(2^K\) possibilities. When \(K\) is at most 100, \(2^{100}\) becomes an astronomical number, making it completely infeasible to compute.

Solution

This is a classic 0-1 knapsack problem. For each vulnerable plant, we have two choices: “install/don’t install”, with the total cost within budget \(M\), maximizing the total value. This can be solved efficiently using dynamic programming (DP).

Algorithm

Step 1: Classifying Plants

Divide each plant into two groups based on drought tolerance. - If \(B_i \geq T\), it’s safe → Add ornamental value to safe_value - If \(B_i < T\), it’s vulnerable → Add to the list vulnerable

Step 2: 0-1 Knapsack DP

For vulnerable plants, perform the following DP:

• \(dp[j]\) = maximum value obtainable within cost \(j\)

Transition formula (when considering plant \((value, cost) = (v, c)\)): $\(dp[j] = \max(dp[j], dp[j - c] + v) \quad (j \geq c)\)$

Important: Since each plant can only be selected once, update \(j\) from larger to smaller values (reverse order update).

Concrete Example

When \(M = 5\) and there are 2 vulnerable plants: \((value=10, cost=3)\) and \((value=7, cost=2)\):

Initial state: \(dp = [0, 0, 0, 0, 0, 0]\)

After processing plant 1 \((10, 3)\): \(dp = [0, 0, 0, 10, 10, 10]\)

After processing plant 2 \((7, 2)\): \(dp = [0, 0, 7, 10, 10, 17]\)

The answer is \(dp[5] = 17\) (select both, cost \(3+2=5\))

Step 3: Final Result

\[\text{Answer} = \text{safe\_value} + dp[M]\]

Complexity

• Time complexity: \(O(N \cdot M)\)
  • For each vulnerable plant (at most \(N\)), loop up to cost \(M\)
• Space complexity: \(O(M)\)
  • Size of the DP table

Implementation Notes

• Reverse order update is essential: In the 0-1 knapsack, to avoid selecting the same plant multiple times, we loop in reverse order with for j in range(M, cost - 1, -1). If we iterate forward, we might select the same plant multiple times.
• 1D DP is sufficient: By using reverse order update, we can implement with a 1D array instead of a 2D array, improving space efficiency.

Source Code

def solve():
    N, M, T = map(int, input().split())
    
    plants = []
    for i in range(N):
        A, B, C = map(int, input().split())
        plants.append((A, B, C))
    
    # Divide plants into two groups
    # Group 1: Drought tolerance >= T (won't wither even without irrigation equipment)
    # Group 2: Drought tolerance < T (will wither without irrigation equipment)
    
    safe_value = 0  # Total value of plants that survive without irrigation equipment
    vulnerable = []  # List of plants that wither without irrigation equipment (value, cost)
    
    for A, B, C in plants:
        if B >= T:
            # This plant won't wither even without irrigation equipment
            safe_value += A
        else:
            # This plant will wither without irrigation equipment
            vulnerable.append((A, C))
    
    # Solve the knapsack problem for vulnerable plants
    # Find the maximum value of plants that can be selected within budget M
    
    # dp[j] = maximum value obtainable within cost j
    dp = [0] * (M + 1)
    
    for value, cost in vulnerable:
        # Update in reverse order (0-1 knapsack)
        for j in range(M, cost - 1, -1):
            dp[j] = max(dp[j], dp[j - cost] + value)
    
    # Maximum value is safe_value + dp[M]
    print(safe_value + dp[M])

solve()

---

This editorial was generated by claude4.5opus.