[ABC224] B - Mongeness (Monge解法)
[Q] https://atcoder.jp/contests/abc224/tasks/abc224_b
O(N^4) 探索すればいいんだけど、O(N^2)で十分という知見。
1. 2*2の正方形の探索をするだけでよかった。
Q.
1 2 3
4 5 6
7 8 9
について。
・次の4通りだけ調べればいい。
(1,2,1,2)
(1,2,2,3)
(2,3,1,2)
(2,3,2,3)
1 2 2 3
4 5 5 6
4 5 5 6
7 8 8 9
・そうしておけば、たとえば
(1,3,1,2)
1 2
4 5
7 8
は、次の2要素の和になっている。
(1,2,1,2) + (2,3,1,2)
1 2
4 5
4 5
7 8
1 + 5 + 4 + 8 - 2 - 4 - 5 - 7 // 4 と 5 が打ち消しあう
= 1 + 8 - 2 - 7実装
int main(){
cincout();
ll H, W;
cin >> H >> W;
ll A[55][55];
rep(i, H) rep(j, W) cin >> A[i][j];
bool ok = true;
rep(i, H-1) rep(j, W-1){
if (A[i][j] + A[i+1][j+1] > A[i][j+1] + A[i+1][j]){
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
}