B - Mongeness

コンテスト時間: 2021-10-23(土) 12:00 ~ 2021-10-23(土) 13:40 (100分) AtCoderホームへ戻る

B - Mongeness 解説

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : $200$ 点

問題文

縦 $H$ 行、横 $W$ 列のマス目があり、各マスには $1$ つの整数が書かれています。上から $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 と出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

Yes

$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 を出力します。

入力例 2Copy

Copy

2 4
4 3 2 1
5 6 7 8

出力例 2Copy

Copy

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}$ です。

Score : $200$ points

Problem Statement

We have a grid with $H$ horizontal rows and $W$ vertical columns, where each square contains an integer. The integer written on the square at the $i$ -th row from the top and $j$ -th column from the left is $A_{i, j}$ .

Determine whether the grid satisfies the condition below.

$A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2}$ holds for every quadruple of integers $(i_1, i_2, j_1, j_2)$ such that $1 \leq i_1 < i_2 \leq H$ and $1 \leq j_1 < j_2 \leq W$ .

Constraints

$2 \leq H, W \leq 50$
$1 \leq A_{i, j} \leq 10^9$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

If the grid satisfies the condition in the Problem Statement, print Yes; otherwise, print No.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

Yes

There are nine quadruples of integers $(i_1, i_2, j_1, j_2)$ such that $1 \leq i_1 < i_2 \leq H$ and $1 \leq j_1 < j_2 \leq W$ . For all of them, $A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2}$ holds. Some examples follow.

For $(i_1, i_2, j_1, j_2) = (1, 2, 1, 2)$ , we have $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}$ .
For $(i_1, i_2, j_1, j_2) = (1, 2, 1, 3)$ , we have $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}$ .
For $(i_1, i_2, j_1, j_2) = (1, 2, 2, 3)$ , we have $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}$ .
For $(i_1, i_2, j_1, j_2) = (1, 3, 1, 2)$ , we have $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}$ .
For $(i_1, i_2, j_1, j_2) = (1, 3, 1, 3)$ , we have $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}$ .

We can also see that the property holds for the other quadruples: $(i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3)$ .
Thus, we should print Yes.

Sample Input 2Copy

Copy

2 4
4 3 2 1
5 6 7 8

Sample Output 2Copy

Copy

No

We should print No because the condition is not satisfied.
This is because, for example, we have $A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2}$ for $(i_1, i_2, j_1, j_2) = (1, 2, 1, 4)$ .