A97291.风祭城的碑阵刻印
普及+/提高
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
风祭城广场上铺着一座 n×m 的符文碑阵。第 i 行第 j 列的碑面需要刻下恰好 Aij 道灵痕才能激活。祭司从一座全空碑阵出发,只能使用两种法印:
- 横风印:选择一整行,使该行每块碑面灵痕数都 +1;
- 竖泉印:选择一整列,使该列每块碑面灵痕数都 +1。
印法可重复、顺序任意。请判断:是否存在一系列印法,使最终碑阵恰好与给定的矩阵 A 一致。
输入格式
- 第一行两个整数 n,m;
- 接下来 n 行,每行 m 个整数,表示矩阵 A。
输出格式
- 若不可达,输出一行:
NO; - 若可达,输出两行:
- 第 1 行:
YES; - 第 2 行:最少操作次数(一个整数)。
- 第 1 行:
输入输出样例
输入#1
2 3 1 4 2 2 5 3
输出#1
YES 7
输入#2
2 2 0 1 2 0
输出#2
NO
说明/提示
| 测试点 | n⋅m 范围 | Aij 范围 |
|---|---|---|
| 1∼2 | 1≤n⋅m≤200 | 0≤Aij≤109 |
| 3∼6 | 200<n⋅m≤5×103 | 0≤Aij≤109 |
| 7∼20 | 5×103<n⋅m≤2×105 | 0≤Aij≤109 |