分数: 700 点
问题陈述
我们有一个 H \times W 网格,其中每个方格上写有一个整数。 对于 1\leq i\leq H 和 1\leq j\leq W,让 A_{i,j} 表示写在正方形上的整数 i第行和 j第列。
您可以执行以下操作任意次数(可能为零)。
- 选择整数 i 和 j 这样 1\leq i\leq H - 1 和 1\leq j\leq W - 1.
- 选择另一个整数 x.
- 添加 x 至每个 A_{i,j}, A_{i,j+1}, A_{i+1,j},和 A_{i+1,j+1}.
打印以下的最小可能值 操作后的 \sum_{i=1}^H \sum_{j=1}^W |A_{i,j}| ,以及达到该值时网格上的整数。
约束
- 2\leq H, W \leq 500
- |A_{i,j}|\leq 10^9
输入
输入由标准输入按以下格式给出:
H W
A_{1,1} \ldots A_{1,W}
\vdots
A_{H,1} \ldots A_{H,W}
输出
打印 H + 1 行。 的 1-st 行应包含以下值 \sum_{i=1}^H \sum_{j=1}^W |A_{i,j}|。 的 网格的 2-nd 通过 (H+1)第行应包含网格上的整数,格式如下:
A_{1,1} \ldots A_{1,W}
\vdots
A_{H,1} \ldots A_{H,W}
如果有多个解决方案,您可以打印其中任何一个。
示例输入 1
2 3 1 2 3 4 5 6
示例输出 1
9 0 -3 -1 3 0 2
以下是在示例输出中生成网格的一系列操作。
- 进行操作 (i, j, x) = (1, 1, -1).
- 进行操作 (i, j, x) = (1, 2, -4).
在这里,我们有 \sum_{i=1}^H \sum_{j=1}^W |A_{i,j}| = 0 + 3 + 1 + 3 + 0 + 2 = 9.
示例输入 2
2 2 1000000000 -1000000000 -1000000000 1000000000
示例输出 2
4000000000 2000000000 0 0 2000000000
如果 |A_{i,j}| > 10^9 操作后。
示例输入 3
3 4 0 2 0 -2 -3 -1 2 0 -3 -3 2 2
示例输出 3
0 0 0 0 0 0 0 0 0 0 0 0 0