题解

思路

先比较 $\sum A_i$ 与 $\sum B_j$ 对 $K$ 的余数；二者不同则总和不可能同时满足行列条件。

做法

否则先假设所有格子都是 $K-1$，记第 $i$ 行为了得到余数 $A_i$ 至少还需减少 $C_i$，第 $j$ 列类似地至少需减少 $D_j$，其中每个缺口都取 $[0,K-1]$ 内的代表元。

总减量至少是 $Z=\max(\sum C_i,\sum D_j)$。两侧缺口和模 $K$ 相同，可给较小的一侧某个缺口增加适当的 $K$ 使两侧总和都等于 $Z$，再不断在仍有行缺口和列缺口的交点处减少即可；单格最多减少 $K-1$，所以一定能构造。

复杂度

答案为 $HW(K-1)-Z$，时间复杂度 $O(H+W)$，空间复杂度 $O(1)$（除输入数组外）。