求める値は \(\displaystyle \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}| \) です。各 \(k\) に対し \(\displaystyle \sum_{1\le i < j \le N}|A_{i,k}-A_{j,k}| \) の値を高速に計算することを考えます。

\(k\) を固定しているため、一旦 \(B_i=A_{i,k}\) として式を簡単にします。求める値は \(\displaystyle \sum_{1\le i < j \le N} |B_i-B_j|\) です。

この値は「全ての非順序対 \(\lbrace i,j\rbrace\) に対する \(|B_i-B_j|\) の総和」と捉えられるため、\(B\) を並び替えても値は同じになることが分かります。したがって、\(B\) を昇順に並び替えた列として考えます。

\(B\) が昇順であるとすると、以下の式変形が成り立ちます。

\[ \begin{aligned} &\phantom{=}\sum_{1\le i < j \le N} |B_i-B_j|\\ &=\sum_{1\le i < j \le N} (B_j-B_i)\\ &=\sum_{j=1}^N \sum_{i=1}^{j-1} B_j-\sum_{i=1}^N \sum_{j=i+1}^N B_i\\ &=\sum_{j=1}^N (j-1)B_j -\sum_{i=1}^N (N-i)B_i\\ &=\sum_{i=1}^N (2i-N-1)B_i \end{aligned} \]

以上より、各 \(k\) に対し \(\displaystyle \sum_{i=1}^N (2i-N-1)B_i\) の値を求めてその総和を計算すれば良いことが分かります。

0-indexed で計算する場合この値は \(\displaystyle \sum_{i=0}^{N-1} (2i-N+1)B_i\) になることに注意してください。

実装例(Python3)

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
for k in range(m):
    b = [a[i][k] for i in range(n)]
    b.sort()
    for i in range(n):
        ans += (2 * i - n + 1) * b[i]
print(ans)