Overview

This problem asks for the minimum cost required to equalize the amount of water in \(N\) flower beds, using only operations that add water.

Analysis

The key point of this problem is that “you can only increase the water, not decrease it.”

To make the water amounts in all flower beds equal, you need to raise the water amount of every other flower bed to at least the amount of the flower bed that currently has the most water (the maximum value).

If you try to equalize at an amount greater than the maximum, you would need to add extra water to all flower beds, resulting in unnecessary additional cost. Therefore, to achieve the goal with minimum cost, the optimal strategy is to “set all flower beds’ water amounts to the current maximum value.”

Let’s consider a concrete example. If the water amounts in the flower beds are \([2, 5, 3]\): - The maximum value is \(5\). - 1st flower bed: add \(5 - 2 = 3\) liters - 2nd flower bed: add \(5 - 5 = 0\) liters - 3rd flower bed: add \(5 - 3 = 2\) liters - Total cost: \(3 + 0 + 2 = 5\) yen

In this way, the answer can be found by summing up the “difference from the maximum” for each flower bed.

Algorithm

1. Find the maximum value \(M\) from the given sequence \(A\).
2. For each flower bed \(A_i\), calculate the deficit \(M - A_i\) and compute the total sum.
   • Mathematically, this means computing \(\sum_{i=1}^{N} (M - A_i)\).
   • This can be rewritten as \((M \times N) - (\sum A_i)\), allowing the calculation by subtracting the total sum all at once.

Complexity

• Time complexity: \(O(N)\)
  • Finding the maximum of the sequence takes \(O(N)\), and computing the total sum takes \(O(N)\), so the overall complexity is \(O(N)\). Since \(N \leq 2 \times 10^5\), this is sufficiently fast.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the \(N\) input elements in a list.

Implementation Notes

• Handling large values: When \(N=2 \times 10^5\) and \(A_i=10^9\), the total sum can be up to approximately \(2 \times 10^{14}\). In Python, this is handled automatically as arbitrary-precision integers, so there is no issue. However, in other languages (such as C++), you need to use a 64-bit integer type (e.g., long long).

• Efficient input: Since \(N\) can be large, in Python you can reduce execution time by using techniques such as sys.stdin.read().split() for fast input reading.

  Source Code

import sys

def main():
    # 標準入力からすべてのデータを読み込む
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return
    
    # 1番目の要素が N
    n = int(input_data[0])
    # 2番目以降の要素が A_1, A_2, ..., A_N
    a = list(map(int, input_data[1:]))
    
    # 現在の水の量の最大値を取得
    max_val = max(a)
    # 現在の水の量の合計を取得
    total_sum = sum(a)
    
    # すべての花壇を最大値に合わせるために必要な費用の合計
    # 各花壇について (max_val - A_i) を足し合わせたもの
    # つまり、n * max_val - sum(a) となる
    ans = n * max_val - total_sum
    
    # 結果を出力
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gemini-3-flash-preview.