Overview

This is a problem where you need to find all fruit trees whose height is at most the threshold value \(T\), and calculate the total cost of replanting them.

Analysis

The key observations for this problem are as follows:

Essence of the Problem

• The condition to determine whether each fruit tree “has fallen” is the simple inequality \(H_i \leq T\)
• The answer is obtained by summing up the costs \(C_i\) of all fallen fruit trees

Is a Naive Approach Sufficient?

This problem can be solved by checking each fruit tree once. For each of the \(N\) fruit trees, we check the condition and add the cost only for those that satisfy it. This naive approach has a time complexity of \(O(N)\), which is sufficiently fast.

Verification with a Concrete Example

For example, consider the case where \(N = 4\), \(T = 5\) with the following data: - Heights: \(H = [3, 7, 5, 10]\) - Costs: \(C = [100, 200, 150, 300]\)

Checking each fruit tree in order: - Tree 1: \(H_1 = 3 \leq 5\) → Fallen → Add cost 100 - Tree 2: \(H_2 = 7 > 5\) → Not fallen - Tree 3: \(H_3 = 5 \leq 5\) → Fallen → Add cost 150 - Tree 4: \(H_4 = 10 > 5\) → Not fallen

Total cost = \(100 + 150 = 250\)

Algorithm

1. Initialize a variable total_cost to \(0\) to track the total cost
2. For \(i = 0, 1, \ldots, N-1\), repeat the following:
   • If \(H_i \leq T\), add \(C_i\) to total_cost
3. Output the final total_cost

This algorithm is a simple linear scan that traverses the array only once.

Complexity

• Time complexity: \(O(N)\)
  • Since each fruit tree is checked exactly once
• Space complexity: \(O(N)\)
  • To store the input arrays \(H\) and \(C\)

Implementation Notes

1. Beware of overflow: From the constraints, \(C_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), so the total cost can be as large as approximately \(2 \times 10^{14}\). In Python, there is no need to worry about integer overflow, but in languages such as C++, you need to use the long long type.

2. Check the boundary condition: Note that the condition is \(H_i \leq T\) (using \(\leq\), not \(<\)). Fruit trees whose height is exactly \(T\) also count as fallen.

3. When no trees have fallen: If all fruit trees have heights greater than \(T\), total_cost remains at its initial value of \(0\) and is output as is. This is consistent with the problem’s requirements.

   Source Code

N, T = map(int, input().split())
H = list(map(int, input().split()))
C = list(map(int, input().split()))

total_cost = 0
for i in range(N):
    if H[i] <= T:
        total_cost += C[i]

print(total_cost)

---

This editorial was generated by claude4.5opus.