Overview

For products that could be defective (\(W_i \ge T\)), we choose for each product whether to “apply additional cooling (cost \(C\))” or “ship as-is and incur loss \(D\))”, and minimize the total cost.

Analysis

The key observation is that each product’s decision has absolutely no effect on other products.

• Products with \(W_i < T\) will not become defective regardless
  → Applying additional cooling would just waste \(C\), so in the optimal solution we don’t cool them (doing so would not minimize cost).
• Products with \(W_i \ge T\) could become defective, so there are two options:
  1. Apply additional cooling: payment is \(C\)
  2. Ship without cooling as a defective product: loss is \(D\)

Looking at just this single product, the minimum amount to pay is clearly \(\min(C, D)\).
Therefore, if we let \(bad\) be the number of defective candidates, the answer is
\(bad \times \min(C, D)\)

Naively trying all combinations of “which products to cool” would require checking \(2^N\) possibilities, which is far too slow for \(N \le 2\times 10^5\) (TLE). However, with the above observation, we can solve the problem just by counting the number of defective candidates without any exhaustive search.

Concrete examples: - If \(C=3, D=10\), defective candidates should always be cooled (\(3\) is cheaper) - If \(C=7, D=5\), defective candidates should not be cooled (\(5\) is cheaper) - Therefore, “number of defective candidates × the cheaper option” gives the answer immediately

Algorithm

1. Count the number \(bad\) of elements in the temperature array \(W\) satisfying \(W_i \ge T\).
2. Compute and output \(\text{ans} = bad \times \min(C, D)\).

Complexity

• Time complexity: \(O(N)\) (just a single pass to count)
• Space complexity: \(O(1)\) (constant excluding the input array, or \(O(N)\) in practice for reading input)

Implementation Notes

• Since we only need to count the number of \(W_i \ge T\), sorting is unnecessary.

• In Python, when input is large, reading all at once with sys.stdin.buffer.read() is faster.

• The answer can be as large as \(N \times 10^9\), but Python’s integers have arbitrary precision, so there is no concern about overflow.

  Source Code

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

This editorial was generated by gpt-5.2-high.