AT_tdpc_cat 猫

[problemUrl]: https://atcoder.jp/contests/tdpc/tasks/tdpc_cat 入力は以下の形式で標準入力から与えられる。 > $ N $ $ f_{1,1}\ ...\ f_{1,N} $ $ ... $ $ f_{N,1}\ ...\ f_{N,N} $ 答えを一行に出力せよ。 ``` 3 0 2 3 2 0 -10 3 -10 0 ``` ``` 4 ``` ``` 5 0 -3 5 2 -6 -3 0 6 -3 1 5 6 0 2 0 2 -3 2 0 4 -6 1 0 4 0 ``` ``` 28 ```

N/A

N/A

### Constraints すぬけ君は $ N $ 匹の猫を飼っている。猫 $ i $ と猫 $ j $ の仲のよさは $ f_{i,j} $ である。ある猫の幸福度は、その猫から距離 1 以内にいる猫との仲のよさの総和である。すぬけ君は、猫 1 から猫 $ N $ をこの順に一次元上に配置することにした。(猫 i の座標を $ x_i $ とすると、$ x_i $ は $ x_1\ をみたす実数)　猫の幸福度の総和の最大値を求めよ。 1\