AtCoder Beginner Contest 224 B

https://atcoder.jp/contests/abc224/tasks/abc224_b

問題文通りに書けば十分間に合いますが、
$A_{i_1,j_1} + A_{i_2,j_2} \ge A_{i_1,j_2} + A_{i_2,j_1}$
$A_{i_2,j_1} + A_{i_3,j_2} \ge A_{i_2,j_2} + A_{i_3,j_1}$
が成り立つと、
$A_{i_1,j_1} + A_{i_3,j_2} - A_{i_1,j_2} - A_{i_3,j_1} \ge -A_{i_2,j_2} + A_{i_2,j_1} - A_{i_2,j_1} + A_{i_2,j_2} = 0$
なので、
$A_{i_1,j_1} + A_{i_3,j_2} \ge A_{i_1,j_2} + A_{i_3,j_1}$
が成り立ちます。
これは、要するに長方形を2分割して、それぞれの領域で不等式成り立てば、元の長方形でも成り立つことを意味します。これは横に分割しましたが、縦に分割しても同じです。

f:id:inamori:20211025224531p:plain

このように分割していけば、長さ1の正方形で不等式が成り立てば、全ての長方形で成り立つことになります。

以下は、PyPy2のコードです。

# coding: utf-8
# Mongeness

from itertools import product


#################### library ####################

def read_int():
    return int(raw_input())

def read_tuple():
    return tuple(map(int, raw_input().split()))

def read_list():
    return list(map(int, raw_input().split()))


#################### naive ####################


#################### process ####################

def read_input():
    H, W = read_tuple()
    A = [ read_list() for _ in range(H) ]
    return A

def F(A):
    H, W = len(A), len(A[0])
    return all(A[j][i] + A[j+1][i+1] <= A[j+1][i] + A[j][i+1]
                    for i, j in product(range(W-1), range(H-1)))


#################### main ####################

A = read_input()
if F(A):
    print 'Yes'
else:
    print 'No'