Overview

All fruit trees with height at most the threshold \(T\) have fallen, so the problem asks to sum up and output the restoration costs \(C_i\) for those trees.

Analysis

The key observation is that “whether a tree has fallen can be determined independently for each tree by checking \(H_i \leq T\).”
In other words, there is no need to consider relationships between trees (ordering or combinations); simply summing the costs of those that satisfy the condition gives the answer.

Even though this seems straightforward, the following roundabout approaches would introduce unnecessary overhead:

• Collecting the indices of fallen trees into a separate array and then traversing that array again to compute the sum (results in two passes, which is unnecessary)
• Sorting by height and searching for “the range \(\leq T\)” (becomes \(O(N \log N)\), which is unnecessary for this simple condition check)

Since \(N \le 2 \times 10^5\) in this problem, an \(O(N)\) solution that computes the sum in a single loop is the most straightforward and reliable approach.
For example, if \(H=[3,10,5],\ T=5,\ C=[100,200,300]\), then the trees that fall have heights \(3\) and \(5\), so the total is \(100+300=400\).

Algorithm

1. Read the input: \(N, T\), array \(H\), and array \(C\).
2. Initialize an answer variable \(ans=0\).
3. For each \(i=1..N\), if \(H_i \le T\), add \(C_i\) to \(ans\).
4. Output \(ans\).

In the implementation, using zip(H, C) makes it easy to extract each corresponding pair \((H_i, C_i)\).

Complexity

• Time complexity: \(O(N)\) (each fruit tree is checked and potentially added once)
• Space complexity: \(O(N)\) (for storing the input arrays \(H, C\))

Implementation Notes

• The total can grow up to \(2 \times 10^{14}\), but Python’s int supports arbitrary-precision integers, so there is no risk of overflow (in other languages, long long or equivalent would be required).

• Since the input can be large, using sys.stdin.readline allows for faster reading.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, T = map(int, input().split())
    H = list(map(int, input().split()))
    C = list(map(int, input().split()))
    ans = 0
    for h, c in zip(H, C):
        if h <= T:
            ans += c
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.