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

3 3
2 1 4
3 1 3
6 4 1

Yes

2 4
4 3 2 1
5 6 7 8

No

提示

$2 \leq H, W \leq 50$ $1 \leq A_{i, j} \leq 10^9$ 输入中的所有数值均为整数。存在九组满足 1 \leq i_1 &lt; i_2 \leq H 且 1 \leq j_1 &lt; 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) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3)$。
因此，我们应当输出 $Yes$.
我们应当输出 $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 &gt; 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2}$。

标签: AtCoder|abc224B

来源

AtCoder|abc224B