分数: 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).