/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 333 点
問題文
高橋君は、ある地域の都市計画を担当することになりました。この地域には N 個の都市があり、それぞれの都市には 1 から N までの番号が付けられています。
各都市 i（1 \leq i \leq N）の位置は M 次元空間上の整数座標で表され、その第 k 次元の座標値を A_{i,k} とします（1 \leq k \leq M）。
高橋君は、2つの都市間の距離をマンハッタン距離で定義しています。すなわち、都市 i と都市 j の距離は \displaystyle\sum_{k=1}^{M} |A_{i,k} - A_{j,k}| です。
高橋君は、異なる2都市の順序なしの組すべてについて距離を計算し、その総和を求めたいと考えています。
具体的には、次の値を求めてください。
\sum_{1 \leq i < j \leq N} \sum_{k=1}^{M} |A_{i,k} - A_{j,k}|
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 10
- -10^6 \leq A_{i,k} \leq 10^6
- N, M, A_{i,k} はすべて整数
- 答えは符号付き64ビット整数（2^{63} - 1 以下の非負整数）に収まることが保証される
入力
N M
A_{1,1} A_{1,2} \ldots A_{1,M}
A_{2,1} A_{2,2} \ldots A_{2,M}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,M}
- 1 行目には、都市の個数 N と座標の次元数 M が、スペース区切りで与えられる。
- 続く N 行のうち i 番目の行（1 \leq i \leq N）には、都市 i の M 次元の座標値 A_{i,1}, A_{i,2}, \ldots, A_{i,M} がスペース区切りで与えられる。
出力
すべての異なる2都市の組についてのマンハッタン距離の総和を、整数として 1 行で出力せよ。
入力例 1
3 2 1 2 4 6 7 1
出力例 1
22
入力例 2
2 1 3 10
出力例 2
7
入力例 3
6 3 1 0 3 5 2 1 -3 4 7 2 -1 0 6 3 5 -1 2 4
出力例 3
146
入力例 4
10 4 100 -200 300 -400 -150 250 -350 450 200 -100 400 -300 -250 150 -450 350 300 -300 200 -200 -100 400 -100 500 50 -50 150 -150 -350 350 -250 250 400 -400 100 -100 -200 200 -300 300
出力例 4
62500
入力例 5
2 1 -1000000 1000000
出力例 5
2000000
Score : 333 pts
Problem Statement
Takahashi has been put in charge of urban planning for a certain region. This region has N cities, each numbered from 1 to N.
The position of each city i (1 \leq i \leq N) is represented by integer coordinates in M-dimensional space, where A_{i,k} denotes the coordinate value in the k-th dimension (1 \leq k \leq M).
Takahashi defines the distance between two cities using the Manhattan distance. That is, the distance between city i and city j is \displaystyle\sum_{k=1}^{M} |A_{i,k} - A_{j,k}|.
Takahashi wants to compute the distances for all unordered pairs of distinct cities and find their total sum.
Specifically, compute the following value:
\sum_{1 \leq i < j \leq N} \sum_{k=1}^{M} |A_{i,k} - A_{j,k}|
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 10
- -10^6 \leq A_{i,k} \leq 10^6
- N, M, A_{i,k} are all integers
- It is guaranteed that the answer fits in a signed 64-bit integer (a non-negative integer at most 2^{63} - 1)
Input
N M
A_{1,1} A_{1,2} \ldots A_{1,M}
A_{2,1} A_{2,2} \ldots A_{2,M}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,M}
- The first line contains the number of cities N and the number of dimensions M, separated by a space.
- The i-th of the following N lines (1 \leq i \leq N) contains the M-dimensional coordinate values of city i: A_{i,1}, A_{i,2}, \ldots, A_{i,M}, separated by spaces.
Output
Output the total sum of Manhattan distances over all unordered pairs of distinct cities, as a single integer on one line.
Sample Input 1
3 2 1 2 4 6 7 1
Sample Output 1
22
Sample Input 2
2 1 3 10
Sample Output 2
7
Sample Input 3
6 3 1 0 3 5 2 1 -3 4 7 2 -1 0 6 3 5 -1 2 4
Sample Output 3
146
Sample Input 4
10 4 100 -200 300 -400 -150 250 -350 450 200 -100 400 -300 -250 150 -450 350 300 -300 200 -200 -100 400 -100 500 50 -50 150 -150 -350 350 -250 250 400 -400 100 -100 -200 200 -300 300
Sample Output 4
62500
Sample Input 5
2 1 -1000000 1000000
Sample Output 5
2000000