AT_abc224_b [ABC224B] Mongeness

题目描述

有一个纵向 $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}$。

输入格式

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

$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

输入 #1

3 3
2 1 4
3 1 3
6 4 1

输出 #1

Yes

输入输出样例 #2

输入 #2

2 4
4 3 2 1
5 6 7 8

输出 #2

No

说明/提示

限制条件

• $2 \leq H, W \leq 50$
• $1 \leq A_{i,j} \leq 10^9$
• 输入均为整数

样例解释 1

满足 $1 \leq i_1 < i_2 \leq H$ 且 $1 \leq j_1 < j_2 \leq W$ 的整数组 $(i_1, i_2, j_1, j_2)$ 一共有 $9$ 个，对于它们都成立 $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

不满足题目中的条件，因此输出 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}$。

由 ChatGPT 4.1 翻译