AT_rcl_contest_2021_b マッサージチェア2021

[problemUrl]: https://atcoder.jp/contests/rcl-contest-2021/tasks/rcl_contest_2021_b 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) $ から [マンハッタン距離](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%B3%E3%83%8F%E3%83%83%E3%82%BF%E3%83%B3%E8%B7%9D%E9%9B%A2) が $ 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\ 
                            

出力は $ 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\ 
                            

### テストケースの生成について 各ケースはテストケースジェネレータによって生成されています。 テストケースジェネレータはページ下部のリンクより提供しています。 テストケースジェネレータは以下の手順でケースを生成します。厳密には実装を見てください。説明・実装ともに、必ずしも目を通す必要はありません。 - $ E_{\ i,j\ } $ が $ x $ になる確率は、 $ 1/x^2 $ に比例するように生成されます。すなわち、$ E_{\ i,j\ } $ が大きな値になるほど、出現する頻度が低くなります。 ### 配布物について テストケースジェネレータ・テスター・サンプル入力データ・ビジュアライザを次のリンクから提供しています。 [テストケースジェネレータ・テスター・サンプル入力データ・ビジュアライザ (zip)](https://img.atcoder.jp/rcl-contest-2021/005883cbd767ff24197df17a19959035.zip) ### ビジュアライザの説明 入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。 - このビジュアライザはデスクトップ版の [Google Chrome](https://www.google.co.jp/chrome/) および [Mozilla Firefox](https://www.mozilla.org/firefox/new/) の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。 - このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。 - このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。 ビジュアライザは配布物にも含まれ、使用方法については配布物内のREADME.htmlに記述があります。 ### Sample Explanation 1 このケースは説明用のもので、入力の制約（ $ N\ =\ 40 $ ）を満たしていません。 $ 2\ \times\ 1\ +\ 5\ \times\ 1\ +\ 16\ \times\ 4\ =\ 71 $ がスコアとなります。\*\*パワー\*\*に $ N $ より大きな整数を設定できないことに注意してください。 ### Sample Explanation 2 このケースは、テスターに同梱している `input\_0.txt` と同じものです。\*\*性能\*\*が高いものほど、出現頻度が低くなります。 出力例は省略します。