Overview

For each defective product (a product with internal temperature \(T\) or higher), we choose the cheaper option between “applying additional cooling treatment (cost \(C\))” and “shipping as-is (loss \(D\))”, thereby minimizing the total cost.

Analysis

Key Insight

In this problem, each product can be judged independently. That is, whether or not to apply cooling treatment to a given product has no effect on the decisions for other products.

We classify products into the following two types:

• Products with internal temperature less than \(T\): These are not defective to begin with, so they incur a cost of \(0\) without doing anything. Applying cooling treatment would only waste cost \(C\), so doing nothing is optimal.
• Products with internal temperature \(T\) or higher (defective products): There are two options:
  • Apply additional cooling treatment → cost \(C\) is incurred
  • Ship as-is → loss \(D\) is incurred

For each defective product, we simply choose the smaller of \(C\) and \(D\).

Concrete Example

For example, consider the case where \(N=4, T=50, C=3, D=5\) and the internal temperatures are \(W = [30, 60, 80, 40]\).

Product	Temperature	Defective?	Optimal Choice	Cost
1	30	No	Do nothing	0
2	60	Yes	Cooling treatment (\(\min(3,5) = 3\))	3
3	80	Yes	Cooling treatment (\(\min(3,5) = 3\))	3
4	40	No	Do nothing	0

The total cost is \(0 + 3 + 3 + 0 = 6\).

If \(C = 7, D = 5\), then it is cheaper to ship defective products as-is (\(\min(7,5) = 5\)), so we accept a loss of \(5\) per defective product.

Is a Naive Approach Sufficient?

Since we only need to examine each of the \(N\) products once, \(O(N)\) is sufficiently fast. There is no need for an approach that enumerates all combinations (\(2^N\) possibilities).

Algorithm

1. For each product \(i\), determine whether the internal temperature \(W_i\) is \(T\) or higher.
2. If \(W_i \geq T\) (defective), add \(\min(C, D)\) to the running total.
3. If \(W_i < T\), the cost is \(0\), so do nothing.
4. Output the final total.

Complexity

• Time complexity: \(O(N)\) — just a single pass through all products
• Space complexity: \(O(N)\) — for storing the input array (can be reduced to \(O(1)\) by reading input sequentially)

Implementation Notes

• Since both \(C\) and \(D\) can be up to \(10^9\) and the number of defective products can be up to \(2 \times 10^5\), the total can be as large as approximately \(2 \times 10^{14}\). In C++ and similar languages, you need to use long long, but in Python there is no need to worry about integer overflow.

• Although the problem statement technically allows applying cooling treatment to products with internal temperature less than \(T\), this only unnecessarily increases the cost, so it is sufficient to only consider defective products.

  Source Code

N, T, C, D = map(int, input().split())
W = list(map(int, input().split()))

total = 0
for w in W:
    if w >= T:
        total += min(C, D)

print(total)

---

This editorial was generated by claude4.6opus-thinking.