Overview

This problem asks you to identify fruit trees that have been knocked down by a typhoon (those with height \(T\) or less) and calculate the total cost required to replant all of them.

Analysis

What needs to be done in this problem is very straightforward. For each fruit tree \(i\), repeat the following steps:

1. Check whether the height \(H_i\) of fruit tree \(i\) is at most the threshold \(T\).
2. If \(H_i \leq T\), the tree has fallen, so add its restoration cost \(C_i\) to the running total.
3. After checking all fruit trees, output the total.

Notes: - Constraints and Complexity: The number of fruit trees \(N\) is at most \(2 \times 10^5\). If we check each tree one by one (linear scan), the number of operations is proportional to \(N\), which is well within the time limit. - Size of Values: The total cost can reach up to \(2 \times 10^{14}\). Python handles large integers automatically, but in other languages (such as C++), you need to use a 64-bit integer type (e.g., long long).

Algorithm

1. Initialize a variable total_cost to \(0\) to hold the total cost.
2. For each fruit tree \(i = 1, 2, \ldots, N\), perform the following in order:
   • If \(H_i \leq T\), add \(C_i\) to total_cost.
   • Otherwise (if \(H_i > T\)), do nothing.
3. Output the final value of total_cost.

Complexity

• Time Complexity: \(O(N)\) Since we scan each of the \(N\) fruit trees exactly once, the processing completes in time proportional to the number of trees.
• Space Complexity: \(O(N)\) Since we store the height \(H_i\) and cost \(C_i\) of all fruit trees in lists, the memory usage is proportional to the input size.

Implementation Tips

• Efficient Input: Since \(N\) can be as large as \(2 \times 10^5\), calling input() repeatedly in Python may result in long execution times. Using sys.stdin.read().split() to read all input at once and process it as a list can significantly speed things up.

• Type Conversion: Since input data is read as strings, you must convert them to integers using int() before performing comparison operations (<=) or addition.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリスト化します
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return
    
    # N: 果樹の本数, T: 台風の影響を受ける高さの閾値
    N = int(input_data[0])
    T = int(input_data[1])
    
    # H: 各果樹の高さのリスト (インデックス 2 から N+1 まで)
    # C: 各果樹の復旧コストのリスト (インデックス N+2 から 2*N+1 まで)
    H = input_data[2:N+2]
    C = input_data[N+2:2*N+2]
    
    total_cost = 0
    
    # 各果樹について、高さが T 以下であればコストを加算します
    for i in range(N):
        # 比較のために整数型に変換します
        if int(H[i]) <= T:
            total_cost += int(C[i])
            
    # 合計コストを出力します
    print(total_cost)

if __name__ == "__main__":
    solve()

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