B - Mongeness

得分: 200分

问题描述

我们有一个 $H$ 行 $W$ 列的网格，每个格子中都包含一个整数。 第 $i$ 行第 $j$ 列的格子中的整数记作 $A_{i, j}$。

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

对于任意满足 $1 \leq i_1 < i_2 \leq H$ 和 $1 \leq j_1 < j_2 \leq W$ 的四个整数 $(i_1, i_2, j_1, j_2)$，都满足 $A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2}$。

约束

• $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。

3 3
2 1 4
3 1 3
6 4 1

Yes

总共有 $9$ 组满足 $1 \leq i_1 < i_2 \leq H$ 和 $1 \leq j_1 < j_2 \leq W$ 的四个整数 $(i_1, i_2, j_1, j_2)$。对于其中的每一组，都满足 $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)$，条件也是满足的：$(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 4
4 3 2 1
5 6 7 8

No

我们应该输出 No，因为条件不满足。
例如，对于 $(i_1, i_2, j_1, j_2) = (1, 2, 1, 4)$，我们有 $A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2}$。