← 返回题目列表

AtCoder · arc135_d

D. 添加到广场

中文机器翻译题面 查看原题

分数: 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