← 返回题目列表

AtCoder · pakencamp_2025_day1_i

I. 最大距离

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

配点 : 400 点

問題文

M 在维度空间中 N 点 1,2,...,N 和点 i 的坐标是 (A_{i,1}, A_{i,2}, ... , A_{i,M}) 。

与这些不同 2 当您选择一个点时 2 找到点之间的最大曼哈顿距离。

这里,有 2 点 (P_1, P_2, ... , P_M) 和 按字典顺序比较 (Q_1, Q_2, ... , Q_M) 的曼哈顿距离是 |P_i - Q_i| (1 \leq i \leq M)。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 2 \leq N \times M \leq 2 \times 10^5
  • -10^9 \leq A_{i,j} \leq 10^9 (1 \leq i \leq N, 1 \leq j \leq M)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
A_{1,1} A_{1,2} ... A_{1,M}
A_{2,1} A_{2,2} ... A_{2,M}
\vdots
A_{N,1} A_{N,2} ... A_{N,M}

出力

打印答案。 来自


入力例 1

4 3
2 3 2 
2 1 6 
1 4 7 
0 0 5 

出力例 1

8

下面将曼哈顿距离简称为距离。 这时,

  • 点 1 和点 2 的距离是 给出 |2 - 2| + |3 - 1| + |2 - 6| = 6
  • 点 1 和点 3 的距离是 给出 |2 - 1| + |3 - 4| + |2 - 7| = 7
  • 点 1 和点 4 的距离是 给出 |2 - 0| + |3 - 0| + |2 - 5| = 8
  • 点 2 和点 3 的距离是 给出 |2 - 1| + |1 - 4| + |6 - 7| = 5
  • 点 2 和点 4 的距离是 给出 |2 - 0| + |1 - 0| + |6 - 5| = 4
  • 点 3 和点 4 的距离是 给出 |1 - 0| + |4 - 0| + |7 - 5| = 7

,所以两点之间的距离最大值为 1 和点 4 的距离 8 。


入力例 2

10 4
0 0 0 2 
0 0 0 4 
0 0 0 8 
0 0 1 6 
0 0 3 2 
0 0 6 4 
0 1 2 8 
0 2 5 6 
0 5 1 2 
1 0 2 4 

出力例 2

12

空间的维数为 4 可能不止这些。