概要

不良品（\(W_i \ge T\)）になりうる製品について、「追加冷却する（コスト \(C\)）」か「そのまま出荷して損失 \(D\)）」のどちらが得かを製品ごとに選び、合計金額を最小化します。

考察

重要な観察は、各製品の選択が他の製品に一切影響しないことです。

• \(W_i < T\) の製品は、何もしなくても不良品になりません
  → 追加冷却しても無駄に \(C\) を払うだけなので、最適解では冷却しません（しても最小化にならない）。
• \(W_i \ge T\) の製品は、不良品になり得るので選択肢が2つあります：
  1. 追加冷却する：支払いは \(C\)
  2. 冷却しないで不良品出荷：損失は \(D\)

ここで、この製品1個だけを見れば、支払うべき最小額は明らかに \(\min(C, D)\) です。
したがって、不良品候補の個数を \(bad\) とすると答えは \(bad \times \min(C, D)\) になります。

素朴に「どの製品を冷却するか」を全探索すると、選び方は \(2^N\) 通りで、\(N \le 2\times 10^5\) では到底間に合いません（TLE）。しかし上の観察により、全探索せずに不良品候補の数を数えるだけで解けます。

具体例： - \(C=3, D=10\) なら不良品候補は必ず冷却（\(3\) の方が得） - \(C=7, D=5\) なら不良品候補は冷却しない（\(5\) の方が得） - よって「不良品候補の個数 × 得な方」で一発です

アルゴリズム

1. 温度配列 \(W\) のうち、\(W_i \ge T\) を満たす個数 \(bad\) を数える。
2. \(\text{ans} = bad \times \min(C, D)\) を計算して出力する。

計算量

• 時間計算量: \(O(N)\)（1回走査して数えるだけ）
• 空間計算量: \(O(1)\)（入力配列を除けば定数、または実装上は読み込みに \(O(N)\)）

実装のポイント

• \(W_i \ge T\) の個数を数えるだけなので、ソートなどは不要です。

• Pythonでは入力が大きいので、sys.stdin.buffer.read() でまとめて読み込むと高速です。

• 答えは最大で \(N \times 10^9\) 程度になり得ますが、Pythonの整数は多倍長なのでオーバーフローの心配はありません。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, T, C, D = data[0:4]
    W = data[4:4+N]
    bad = sum(1 for x in W if x >= T)
    ans = bad * min(C, D)
    print(ans)

if __name__ == "__main__":
    main()

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