Overview

Given the \(M\)-dimensional coordinates of \(N\) cities, we want to efficiently compute the sum of Manhattan distances \(\sum_{k=1}^{M}|A_{i,k}-A_{j,k}|\) over all pairs \((i<j)\).

Analysis

Since Manhattan distance is the sum of absolute differences per dimension, the total sum can also be decomposed by dimension.

[ \sum{1 \le i < j \le N}\sum{k=1}^{M}|A{i,k}-A{j,k}| = \sum{k=1}^{M}\sum{1 \le i < j \le N}|A{i,k}-A{j,k}| ]

In other words, we just need to “solve the 1-dimensional problem (sum of \(|x_i-x_j|\) over all pairs) \(M\) times and add the results.”

However, naively enumerating all pairs, the number of pairs is \(\binom{N}{2}\approx 2\times 10^5 \times 10^5\), which is extremely large, resulting in [ O(N^2M) ] which will certainly not fit within the time limit (TLE).

Instead, for each dimension, we compute [ \sum_{i}|x_i-x_j| ] in \(O(N\log N)\) using sorting and prefix sums.

Key Insight in One Dimension

Sort the sequence \(x\) in ascending order to get \(a_0 \le a_1 \le \dots \le a_{N-1}\). Then for \(i<j\), we always have \(|a_j-a_i|=a_j-a_i\).

Therefore, considering how many times each \(a_i\) appears in differences with elements to its left:

• \(a_i\) appears as the “larger side” in differences with the \(i\) elements to its left
  → Contribution is \(\sum_{t=0}^{i-1} (a_i-a_t)= i\cdot a_i - \sum_{t=0}^{i-1}a_t\)

Summing this for \(i=0..N-1\) gives the total sum of differences over all pairs.

Concrete example: For \([1, 4, 6]\)
- \(i=0\): contribution \(0\)
- \(i=1\): \(1\cdot 4 - (1)=3\) (pair (1,4))
- \(i=2\): \(2\cdot 6 - (1+4)=7\) (sum of pairs (1,6) and (4,6))
Total \(3+7=10\), which matches \(|1-4|+|1-6|+|4-6|=3+5+2=10\).

Algorithm

1. Collect the input into arrays dims[k] for each dimension (the \(k\)-th dimension values of cities \(1..N\)).
2. For each dimension \(k=1..M\), do the following:
   1. Sort dims[k] in ascending order to obtain arr.
   2. Maintain pref as the “running sum of elements seen so far (prefix sum)”.
   3. Iterate through arr from left to right, and for the value x at position i, add the contribution [ x\cdot i - \text{pref} ] (then update pref).
   4. The resulting value is \(\sum_{i<j}|A_{i,k}-A_{j,k}|\) for that dimension.
3. Sum the results across all dimensions and output.

Complexity

• Time complexity: \(O\big(M \cdot N \log N\big)\) (sorting is required for each dimension)
• Space complexity: \(O(MN)\) (storing values for each dimension)

Implementation Notes

• Independent per dimension: Since Manhattan distance is the sum across dimensions, we can compute each dimension separately and just add the results.

• Sorting removes the absolute value: By sorting in ascending order, for \(i<j\) we have \(|a_j-a_i|=a_j-a_i\), which is easy to handle.

• How to use the prefix sum pref: After computing s += x*i - pref, update with pref += x.

• Fast input for large inputs: The code uses sys.stdin.buffer.read() to read all input at once.

• Watch out for 64-bit overflow: Python’s int does not overflow, but in other languages you need long long or similar.

  Source Code

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)

    dims = [[] for _ in range(M)]
    for _ in range(N):
        for k in range(M):
            dims[k].append(next(it))

    total = 0
    for k in range(M):
        arr = sorted(dims[k])
        pref = 0
        s = 0
        for i, x in enumerate(arr):
            s += x * i - pref
            pref += x
        total += s

    print(total)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.