← 返回题目列表

AtCoder · awc0013_d

D. 城市之间的距离

中文机器翻译题面 查看原题

分数: 333 分

问题陈述

高桥已被任命负责某个地区的城市规划。该地区有 N 城市,每个编号自 1 to N.

各城市位置 i (1 \leq i \leq N) 由整数坐标表示 M维空间,其中 A_{i,k} 表示坐标值 k第维度 (1 \leq k \leq M).

Takahashi 使用以下公式定义两个城市之间的距离 曼哈顿距离。也就是城市之间的距离 i 和城市 j is \displaystyle\sum_{k=1}^{M} |A_{i,k} - A_{j,k}|.

Takahashi 想要计算所有无序对不同城市的距离并求出它们的总和。

具体来说,计算以下值:

\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}
  • 第一行包含城市数量 N 和维数 M,用空格分隔。
  • 的 i- 以下各项 N 行 (1 \leq i \leq N) 包含 M城市维度坐标值 i: A_{i,1}, A_{i,2}, \ldots, A_{i,M},用空格分隔。

输出

将所有无序的不同城市对的曼哈顿距离总和输出为一行上的单个整数。


样本输入 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