DMOPC '22 Contest 3 P5 - Alice Rebalancing

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Alice is playing a game on an N by M grid of integers she got for Christmas, which she calls A. In one move, she can rebalance a row or column. A rebalancing is an operation performed on a row or column. The operation will be described on rows. First, Alice picks a row, and then she picks a cell C in that row. C must have value at least 1. First, she subtracts one from C. Then, she looks for the first zero to the right of C, and adds one to that cell. If no such cell exists, she does no increment, but C is still decremented. Columns are the same, and proceed top-down.

Alice really likes the grid B, because Bob got it for Christmas and she is jealous. Please tell Alice if it is possible to achieve B after some amount of rebalancings.


1 \le N, M \le 100

0 \le A_i, B_i \le 10^9

Subtask 1 [20%]

N = 1

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains 2 space-separated integers N and M.

The next N lines contain M space-separated integers A_{i,j} representing grid A.

The last N lines contain M space-separated integers B_{i,j} representing grid B.

Output Specification

Output YES if B can be achieved after some amount of rebalancings, and NO otherwise.

Sample Input

2 3
2 2 0
0 0 0
0 0 1
0 1 1

Sample Output



There are no comments at the moment.