/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
Xさんが働くオフィスのフリースペースには、N 行 N 列にマッサージチェアが並べられています。
上から i 行目、左から j 列目にあるマッサージチェアの座標を (i, j) と表します。
マッサージチェアには、色々な性能のものがあります。
(i, j) にあるマッサージチェアの性能を 1 以上 30 以下の整数で表したものを E_{i, j} とし、高いほど良いことを意味します。
また、 (i, j) にあるマッサージチェアを動かすパワーとして、 0 以上 N 以下の整数を自由に設定することができ、これを P_{i, j} とします。
- パワーが 0 に設定されたマッサージチェアは使われず、人は座りません。
- パワーが 0 以外に設定されたマッサージチェアには、必ず人が座ります。
- (i, j) にあるマッサージチェアを 0 以外のパワー P_{ i, j } で動かす場合、パワーに応じた動作音が周囲に聞こえてしまうため、 (i, j) から マンハッタン距離 が P_{i, j} 以下の他のマッサージチェアには、人が座らないようにする必要があります。
次の画像は、いくつかのマッサージチェアに 0 以外のパワーを設定した例です。マスに書かれた整数は、その位置にあるマッサージチェアに割り当てられたパワーを表し、ピンク色のマスの位置にあるマッサージチェアには人が座らないようにする必要があります。
Xさんが各マッサージチェアに設定するパワーを決定した後、パワーが 0 でない全てのマッサージチェアに人が座ります。
(i, j) にあるマッサージチェアに座った人は、E_{ i,j } \times P_{ i,j } の満足度を得ます。
マッサージチェアに座った人たちが得る満足度の和を、できるだけ大きくしてください。
各テストケースの得点およびこの問題の得点は、次のように計算されます。
- 1つのテストケースでは、マッサージチェアに座った人たちが得る満足度の総和がそのまま得点になります。
- テストケースは全部で 50 個あります。各テストケースの得点の合計が、この問題の得点になります。
入力
入力は以下の形式で標準入力から与えられます。
1行目には整数 N を一つ含みます。続く N 行のそれぞれには、スペース区切りで整数を N 個含みます。
\(\begin{array}{lll}
N & & \\
E_{ 0,0 } & \ldots & E_{ 0,N-1 } \\
\vdots & \ddots & \vdots \\
E_{ N-1,0 } & \ldots & E_{ N-1,N-1 }
\end{array}\)
- N はマッサージチェアが並ぶ行・列の数を表す整数で、N = 40 を満たします。
- E_{ i,j } は (i, j) にあるマッサージチェアの性能を表す整数で、1 ≤ E_{i,j} ≤ 30 を満たします。
出力
出力は N 行で、各行にはスペース区切りで N 個の整数を標準出力へ出力してください。
\(\begin{array}{lll}
P_{ 0,0 } & \ldots & P_{ 0,N-1 } \\
\vdots & \ddots & \vdots \\
P_{ N-1,0 } & \ldots & P_{ N-1,N-1 }
\end{array}\)
- P_{ i,j } は (i, j) にあるマッサージチェアを動かすパワーを表す整数で、0 ≤ P_{i,j} ≤ N を満たす必要があります。
- 動作音の影響を受けるマッサージチェアは、パワーを必ず 0 に設定してください。
- 出力が上記の制約を満たさない場合、 となります。
テストケースの生成について
各ケースはテストケースジェネレータによって生成されています。
テストケースジェネレータはページ下部のリンクより提供しています。
テストケースジェネレータは以下の手順でケースを生成します。厳密には実装を見てください。説明・実装ともに、必ずしも目を通す必要はありません。
- E_{ i,j } が x になる確率は、 1/x^2 に比例するように生成されます。すなわち、E_{ i,j } が大きな値になるほど、出現する頻度が低くなります。
入力例1
4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16このケースは説明用のもので、入力の制約（ N = 40 ）を満たしていません。
出力例1
0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 42 \times 1 + 5 \times 1 + 16 \times 4 = 71 がスコアとなります。パワーに N より大きな整数を設定できないことに注意してください。
入力例2
40 4 2 1 1 1 1 3 1 1 1 6 1 1 2 1 1 6 17 3 5 1 2 5 2 1 1 1 1 6 12 1 4 1 3 1 1 2 1 3 2 1 1 4 1 1 4 1 1 1 12 3 1 1 1 1 7 1 1 2 1 3 1 11 1 1 1 1 1 1 1 1 1 1 2 1 1 2 4 6 3 5 6 1 1 2 1 3 4 5 1 9 1 1 2 26 6 3 1 1 1 2 4 1 2 1 1 3 1 3 1 1 2 1 1 6 1 2 1 2 1 1 1 1 16 1 1 10 1 1 1 3 7 1 1 1 1 1 2 1 1 1 1 1 19 1 1 2 3 6 1 2 12 1 2 4 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 2 1 1 1 1 9 1 1 1 8 2 2 2 1 1 2 1 1 1 1 2 1 4 1 1 1 2 1 2 1 1 1 1 1 1 1 2 5 1 1 1 3 4 3 1 30 2 1 2 19 1 2 1 1 2 1 3 1 1 1 2 4 1 15 1 4 1 1 1 1 3 4 1 1 2 1 4 1 1 1 2 1 8 8 6 1 2 2 2 2 5 2 1 1 1 1 1 1 1 3 2 1 2 1 1 16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 6 1 3 14 1 1 2 1 1 2 5 6 2 1 14 2 1 1 2 1 1 1 1 1 1 1 2 1 1 19 1 3 1 1 1 4 2 5 1 2 1 1 1 1 9 1 1 1 1 1 1 20 17 1 1 2 4 1 6 1 1 1 2 1 1 1 1 11 5 3 1 1 1 3 3 1 2 3 1 1 4 1 1 1 1 3 1 1 1 2 12 1 5 1 1 2 3 2 21 2 5 1 1 1 3 1 3 1 1 4 3 2 1 1 1 1 1 4 8 1 1 3 1 2 1 1 3 1 1 1 1 4 2 2 1 18 1 1 1 1 1 1 1 1 2 1 1 1 1 3 1 4 1 1 2 1 1 2 2 3 1 6 3 6 4 2 3 1 3 1 3 1 2 1 3 1 1 7 1 5 8 2 1 1 1 3 5 3 2 1 1 1 1 1 6 7 1 1 2 2 1 1 2 1 6 11 2 1 1 1 1 1 1 13 3 1 5 1 1 2 8 1 1 1 1 1 4 1 1 1 10 1 12 1 1 1 7 10 2 1 23 1 1 1 5 8 3 1 1 2 1 1 1 1 1 1 1 1 1 2 1 1 2 1 1 1 9 1 1 1 2 1 1 1 1 9 3 1 1 2 3 1 1 2 1 1 1 7 1 1 2 1 1 1 2 1 1 1 2 2 1 1 2 1 2 2 1 2 1 17 1 5 1 1 1 1 1 1 1 1 2 6 1 1 3 1 1 1 1 6 1 1 1 1 1 2 1 1 2 1 3 3 1 1 2 1 2 1 1 1 2 1 1 1 1 2 1 2 1 1 2 1 2 1 1 5 1 1 1 4 2 2 2 1 1 2 30 4 2 2 1 2 1 1 1 1 1 1 5 1 1 2 1 1 6 1 3 1 3 1 1 1 8 1 1 1 1 1 1 1 2 1 1 1 2 1 1 4 1 1 2 1 10 9 7 7 1 1 2 1 1 1 1 1 2 1 3 2 12 1 6 1 1 1 4 3 1 1 1 1 1 1 1 1 1 1 2 2 1 4 1 1 2 1 7 1 1 2 1 3 15 1 1 1 1 2 1 6 1 1 1 2 3 1 1 1 1 4 7 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 2 1 1 2 2 2 1 4 1 2 1 2 1 2 2 2 1 3 1 1 2 1 2 1 1 3 1 1 1 1 1 1 14 1 1 2 3 2 1 2 1 2 3 2 1 1 2 5 1 3 1 1 1 1 1 2 2 1 9 1 1 4 1 1 2 3 3 1 1 1 2 11 1 1 2 2 1 2 1 1 1 2 1 1 2 1 1 1 2 1 1 13 1 5 1 1 1 1 1 18 2 1 1 1 1 2 2 1 1 6 1 1 1 1 4 1 2 1 1 3 3 1 1 3 1 3 2 1 1 7 1 2 1 1 1 1 3 2 1 7 1 1 1 1 1 1 2 1 1 1 1 1 5 1 14 2 1 1 2 1 2 1 1 1 2 1 2 1 3 1 2 1 1 1 15 13 1 1 1 12 6 1 2 2 1 6 5 1 2 1 3 1 9 1 2 1 3 1 19 1 1 1 1 7 9 1 8 3 3 2 1 1 1 9 1 1 2 1 1 1 3 1 2 1 1 1 21 2 8 1 1 21 1 3 3 4 2 1 2 6 1 1 9 1 1 1 3 1 1 1 8 2 2 2 1 2 1 5 1 8 7 1 1 2 1 1 3 2 10 1 6 7 2 8 1 4 2 1 1 1 1 1 2 1 3 2 1 4 1 1 3 1 2 1 1 1 1 1 1 1 1 1 1 1 1 7 4 8 1 5 17 2 1 2 1 1 1 1 1 1 1 2 2 1 3 1 1 2 2 9 1 1 1 1 3 1 1 2 1 1 7 28 1 5 1 1 1 2 1 2 3 1 2 1 1 1 1 1 2 1 1 1 3 1 3 1 1 1 1 3 1 19 4 1 1 1 2 1 5 1 1 1 1 1 1 2 2 1 3 1 1 1 5 2 2 1 3 1 1 3 1 1 1 1 1 1 1 2 1 1 1 4 1 1 1 4 3 4 1 2 1 3 1 10 1 1 6 2 1 1 1 1 1 1 1 6 2 1 4 2 8 1 5 2 1 1 1 1 1 1 4 1 4 1 1 1 7 1 1 3 30 1 3 1 1 3 1 1 3 2 1 1 1 6 1 1 1 1 1 1 1 2 11 1 1 1 1 1 2 1 1 3 28 5 1 1 1 1 1 1 1 3 11 1 4 1 2 1 1 4 1 6 2 1 1 1 1 1 26 1 1 7 1 2 2 2 2 1 10 1 1 1 2 1 1 2 1 2 1 1 1 1 1 1 1 2 2 3 1 1 1 1 1 1 3 1 4 2 2 1 1 11 4 1 4 5 1 1 1 2 6 17 2 1 4 22 1 9 1 11 25 3 2 1 1 1 2 7 1 2 2 1 2 16 1 2 1 1 3 1 5 3 1 1 1 1 1 1 3 6 1 3 1 4 6 1 3 4 4 1 1 1 2 1 1 1 1 5 1 6 7 1 1 1 1 1 1 1 3 1 2 1 1 1 1 4 3 1 1 1 1 9 1 1 1 1 1 3 1 4 3 1 1 1 4 1 2 1 2 7 1 4 1 1 1 1 3 1 1 1 8 1 1 1 1 1 1 1 2 1 7 2 1 4 1 1 1 3 1 1 1 2 1 6 1 1 1 2 23 4 1 1 1 1 1 1 10 1 1 1 1 1 15 14 1 1 2 1 1 1 2 1 1 5 1 12 17 1 1 1 1 1 1 3 1 1 1 1 1 1 1 7 1 2 1 1 5 4 1 1 1 7 1 3 1 1 2 1 1 1 2 3 2 2 1 1 8 2 1 2 2 2 1 1 2 1 1 1 1 6 1 5 1 1 1 1 1 1 1 3 1 1 1 7 1 2このケースは、テスターに同梱している
input_0.txt と同じものです。性能が高いものほど、出現頻度が低くなります。出力例は省略します。
配布物について
テストケースジェネレータ・テスター・サンプル入力データ・ビジュアライザを次のリンクから提供しています。
ビジュアライザの説明
入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。
- このビジュアライザはデスクトップ版の Google Chrome および Mozilla Firefox の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。
- このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
- このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
ビジュアライザは配布物にも含まれ、使用方法については配布物内のREADME.htmlに記述があります。