Overview

This problem asks you to calculate the height difference (absolute value) for every pair of \(N\) students and find the total sum.

Analysis

Naive Approach

If we examine all pairs \((i, j)\) using a double loop, the number of pairs is \(\frac{N(N-1)}{2}\). With the constraint \(N \leq 2 \times 10^5\), the number of computations reaches approximately \(2 \times 10^{10}\), which will not fit within the time limit (typically about 2 seconds). We need a way to reduce the computational complexity.

Eliminating Absolute Values by Sorting

What makes computing the absolute value \(|A_i - A_j|\) difficult is that the formula changes depending on which height is taller. Here, let’s try sorting the height list \(A\) in ascending order (from smallest to largest). Sorting does not change the answer itself, which is “the sum of differences over all pairs.”

If we denote the sorted array as \(A_0, A_1, \dots, A_{N-1}\), then whenever \(i < j\), we always have \(A_i \leq A_j\). This allows us to remove the absolute value signs and compute \(|A_j - A_i| = A_j - A_i\).

Considering the “Contribution” of Each Element

In the sorted array, we count how each element \(A_i\) contributes to the final total sum.

Focusing on a particular element \(A_i\) (0-indexed): - There are \(i\) elements to its left that are smaller than (or equal to) \(A_i\). In pairs with these elements, \(A_i\) is on the “added side” rather than the “subtracted side,” so it is added a total of \(i\) times. - There are \((N - 1 - i)\) elements to its right that are larger than (or equal to) \(A_i\). In pairs with these elements, \(A_i\) is on the “subtracted side,” so it is subtracted a total of \((N - 1 - i)\) times.

Therefore, the contribution of each \(A_i\) to the total sum can be expressed as: $\(A_i \times (i - (N - 1 - i)) = A_i \times (2i - N + 1)\)$

By computing this expression for all \(i\) and summing them up, we can obtain the answer in \(O(N)\).

Algorithm

1. Sort the input height list \(A\) in ascending order.
2. Initialize a variable ans to \(0\) to hold the total sum.
3. Repeat the following for \(i = 0\) to \(N-1\):
   • Add \(A_i \times (2i - N + 1)\) to ans.
4. Output the final value of ans.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Sorting the heights takes \(O(N \log N)\). The subsequent sum calculation is \(O(N)\), so the overall complexity is dominated by the sorting step.
• Space Complexity: \(O(N)\)
  • An array to store \(N\) elements is required.

Implementation Notes

• Handling Large Numbers: The answer can become a very large value, but since Python natively supports arbitrary-precision integers, you can compute without worrying about overflow.

• Fast Input: Since \(N\) can be large, it is efficient to read all input at once using methods such as sys.stdin.read().split().

  Source Code

import sys

def solve():
    # 入力をすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Nを取得
    n = int(input_data[0])
    # 身長リストAを取得
    a = list(map(int, input_data[1:]))
    
    # 身長を昇順にソートする
    # ソートすることで絶対値記号を外して計算できるようになる
    a.sort()
    
    # 総和を計算する
    # 各要素 a[i] が何回足され、何回引かれるかを考える
    # インデックス i (0-indexed) の要素 a[i] について：
    # 自分より小さい要素は i 個あり、それらとの差では a[i] は正の項になる
    # 自分より大きい要素は (n - 1 - i) 個あり、それらとの差では a[i] は負の項になる
    # したがって、a[i] の係数は i - (n - 1 - i) = 2*i - n + 1 となる
    ans = 0
    for i in range(n):
        ans += (2 * i - n + 1) * a[i]
    
    # 結果を出力
    print(ans)

if __name__ == "__main__":
    solve()

---

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