/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
H\times W のマス目があり、各マスに整数がひとつずつ書き込まれています。 1\leq i\leq H, 1\leq j\leq W に対して、i 行目・j 列目のマスに書き込まれている整数を A_{i,j} で表します。
あなたは次の操作を、何度でも行うことができます（一度も行わなくてもよいです）。
- 1\leq i\leq H - 1 かつ 1\leq j\leq W - 1 を満たす整数 i, j を選ぶ。
- 整数 x をひとつ選ぶ。
- A_{i,j}, A_{i,j+1}, A_{i+1,j}, A_{i+1,j+1} に x を加える。
操作後の \sum_{i=1}^H \sum_{j=1}^W |A_{i,j}| が最小となるように操作を行うとき、操作後の \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 行目には、\sum_{i=1}^H \sum_{j=1}^W |A_{i,j}| の値を出力してください。 2 行目から 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
Score : 700 points
Problem Statement
We have an H \times W grid, where each square has one integer written on it. For 1\leq i\leq H and 1\leq j\leq W, let A_{i,j} denote the integer written on the square at the i-th row and j-th column.
You can do the operation below any number of times (possibly zero).
- Choose integers i and j such that 1\leq i\leq H - 1 and 1\leq j\leq W - 1.
- Choose another integer x.
- Add x to each of A_{i,j}, A_{i,j+1}, A_{i+1,j}, and A_{i+1,j+1}.
Print the minimum possible value of \sum_{i=1}^H \sum_{j=1}^W |A_{i,j}| after your operations, and the integers on the grid when that value is achieved.
Constraints
- 2\leq H, W \leq 500
- |A_{i,j}|\leq 10^9
Input
Input is given from Standard Input from the following format:
H W
A_{1,1} \ldots A_{1,W}
\vdots
A_{H,1} \ldots A_{H,W}
Output
Print H + 1 lines. The 1-st line should contain the value of \sum_{i=1}^H \sum_{j=1}^W |A_{i,j}|. The 2-nd through (H+1)-th lines should contain the integers on the grid, in the following format:
A_{1,1} \ldots A_{1,W}
\vdots
A_{H,1} \ldots A_{H,W}
If there are multiple solutions, you may print any of them.
Sample Input 1
2 3 1 2 3 4 5 6
Sample Output 1
9 0 -3 -1 3 0 2
Here is a sequence of operations that produces the grid in the Sample Output.
- Do the operation with (i, j, x) = (1, 1, -1).
- Do the operation with (i, j, x) = (1, 2, -4).
Here, we have \sum_{i=1}^H \sum_{j=1}^W |A_{i,j}| = 0 + 3 + 1 + 3 + 0 + 2 = 9.
Sample Input 2
2 2 1000000000 -1000000000 -1000000000 1000000000
Sample Output 2
4000000000 2000000000 0 0 2000000000
It is fine if |A_{i,j}| > 10^9 after your operations.
Sample Input 3
3 4 0 2 0 -2 -3 -1 2 0 -3 -3 2 2
Sample Output 3
0 0 0 0 0 0 0 0 0 0 0 0 0