← 返回题目列表

AtCoder · abc224_b

C. 蒙赫内斯

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

分数: 200 点

问题陈述

我们有一个网格 H 水平行和 W 垂直列,其中每个方格包含一个整数。 写在方格上的整数 i从顶部开始的第行和 j左起第列是 A_{i, j}.

判断网格是否满足以下条件。

A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} 对于每个整数四元组都成立 (i_1, i_2, j_1, j_2) 这样 1 \leq i_1 < i_2 \leq H 和 1 \leq j_1 < j_2 \leq W.

约束

  • 2 \leq H, W \leq 50
  • 1 \leq A_{i, j} \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}

输出

如果网格满足问题陈述中的条件,则打印 Yes;否则,打印 No.


示例输入 1

3 3
2 1 4
3 1 3
6 4 1

示例输出 1

Yes

有九个四元数 (i_1, i_2, j_1, j_2) 这样 1 \leq i_1 < i_2 \leq H 和 1 \leq j_1 < j_2 \leq W。对于他们所有人来说, A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} 成立。下面是一些例子。

  • 对于 (i_1, i_2, j_1, j_2) = (1, 2, 1, 2),我们有 A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
  • 对于 (i_1, i_2, j_1, j_2) = (1, 2, 1, 3),我们有 A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \leq 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
  • 对于 (i_1, i_2, j_1, j_2) = (1, 2, 2, 3),我们有 A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \leq 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
  • 对于 (i_1, i_2, j_1, j_2) = (1, 3, 1, 2),我们有 A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \leq 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
  • 对于 (i_1, i_2, j_1, j_2) = (1, 3, 1, 3),我们有 A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.

我们还可以看到该属性对于其他四元组也成立: (i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3).
因此,我们应该打印 Yes.


示例输入 2

2 4
4 3 2 1
5 6 7 8

示例输出 2

No

我们应该打印 No 因为条件不满足。
这是因为,例如,我们有 A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2} 为 (i_1, i_2, j_1, j_2) = (1, 2, 1, 4).