概要

高さが基準値 \(T\) 以下の果樹はすべて倒れているので、それらの復旧コスト \(C_i\) を合計して出力する問題です。

考察

重要な観察は「倒れたかどうかは各果樹ごとに独立に \(H_i \leq T\) で判定できる」ことです。
つまり、木同士の関係（並び順や組み合わせ）を考える必要は一切なく、条件を満たすもののコストを足し上げるだけで答えになります。

素朴に見えても、例えば以下のような回りくどい方法を取ると無駄が増えます。

• 倒れた木の番号を別配列に集めてから、もう一度その配列をたどって合計する（2回走査になり不要）
• 高さでソートして「\(T\) 以下の範囲」を探す（\(O(N \log N)\) になり、今回の条件判定には不要）

この問題は \(N \le 2 \times 10^5\) なので、1回のループで合計する \(O(N)\) 解法が最も素直で確実です。
例として、\(H=[3,10,5],\ T=5,\ C=[100,200,300]\) なら、倒れるのは高さ \(3,5\) の木なので合計は \(100+300=400\) です。

アルゴリズム

1. 入力として \(N, T\)、配列 \(H\)、配列 \(C\) を受け取る。
2. 答え用変数 \(ans=0\) を用意する。
3. 各 \(i=1..N\) について、もし \(H_i \le T\) なら \(ans\) に \(C_i\) を加算する。
4. 最後に \(ans\) を出力する。

実装では zip(H, C) を使うと、対応する \((H_i, C_i)\) をペアで取り出せて分かりやすいです。

計算量

• 時間計算量: \(O(N)\)（各果樹を1回ずつ判定して加算）
• 空間計算量: \(O(N)\)（入力配列 \(H, C\) を保持するため）

実装のポイント

• 合計は最大で \(2 \times 10^{14}\) まで増えますが、Python の int は多倍長整数なのでオーバーフローの心配はありません（他言語なら long long 等が必要）。

• 入力が大きいので、sys.stdin.readline を使うと高速に読み取れます。

  ソースコード

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

この解説は gpt-5.2-high によって生成されました。