Overview

This problem asks us to minimize the total amount shaved off to make all apples (after coating) the same weight. In conclusion, the answer is independent of \(R\) and equals \(\sum A_i - N \cdot \min(A_i)\).

Analysis

Key Insight

The weight after coating increases uniformly by \(+R\) for each apple, giving \(B_i = A_i + R\).
When shaving each apple down to make them all equal to \(X\), the amount shaved from each apple is \((B_i - X)\) (where \(X \le B_i\) is required), so the total is

\([ \sum_{i=1}^{N} (B_i - X) = \sum B_i - N X ]\)

This means the larger \(X\) is, the smaller the total (due to the \(-NX\) term), so we should choose the largest possible \(X\).

Since we can only shave (not add), we need \(X \le B_i\) for all apples. Therefore, the maximum possible \(X\) is

\([ X = \min_i B_i ]\)

Why \(R\) Has No Effect

Since \(\min_i B_i = \min_i (A_i + R) = \min_i A_i + R\), we get

\([ \sum B_i - N\min B_i = \left(\sum (A_i + R)\right) - N(\min A_i + R) = \left(\sum A_i + NR\right) - (N\min A_i + NR) = \sum A_i - N\min A_i ]\)

Since \(R\) completely cancels out, the input value of \(R\) does not affect the answer.

Why a Naive Approach Is Risky

For example, if you try various values of \(X\) to find the minimum (via brute force or binary search), the range of \(X\) can be \(10^9\) or more, and \(N\) can be as large as \(2\times10^5\), making this impractical.
With the observation above, once we know that “the optimal \(X\) equals the minimum value,” we can compute the answer directly without any search.

Concrete Example

Given \(A=[3,7,5], R=2\), the weights after coating are \(B=[5,9,7]\).
The maximum \(X\) we can equalize to is \(\min(B)=5\). The total amount shaved is \((5-5)+(9-5)+(7-5)=0+4+2=6\).
Using the formula: \(\sum A - N\min A = (3+7+5) - 3\cdot 3 = 15-9=6\), which matches.

Algorithm

1. Read the input \(A_1,\dots,A_N\) (read \(R\) as well, but it is not needed for the computation).
2. Compute \(m = \min(A)\).
3. Compute \(s = \sum A\).
4. Output the answer \(s - N\cdot m\).

This means “it is optimal to match the lightest apple,” and all other apples are shaved down to that weight.

Complexity

• Time complexity: \(O(N)\) (computing the minimum and the sum once each)
• Space complexity: \(O(N)\) (since the code stores values in an array; with sequential processing, \(O(1)\) is also possible)

Implementation Notes

• The total and \(N\cdot \min(A)\) can be as large as \(2\times10^5 \times 10^9 = 2\times10^{14}\). Python’s int supports arbitrary precision, so this is safe as-is (in other languages, use 64-bit integers).

• Since the input can be large, fast input using sys.stdin.buffer.read() is used.

• While the problem statement has us think in terms of post-coating weights, since \(R\) cancels out in the end, there is no need to include it in the computation.

  Source Code

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    R = next(it)  # not needed for the result
    A = [next(it) for _ in range(N)]
    m = min(A)
    s = sum(A)
    print(s - N * m)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.