← 返回题目列表

AtCoder · tdpc_cat

L. 猫

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

问题陈述

潜伏 我有 N 我有两只猫。猫 i 和猫 j 我们有多接近? f_{i,j} 。猫的幸福度是它与距离为 1 内的猫的友谊总和。Snuke 是来自猫 1 的猫 我决定在一维中按此顺序排列 N 。 (猫 i 的坐标是 x_i 以x_i 是 您也可以写 x_1 < x_2 < ... < x_N 实数)找到猫的幸福水平总和的最大值。

约束

  • 1 ≤ N ≤ 1000
  • -1000 ≤ f_{i,j} ≤ 1000
  • f_{i,i} = 0
  • f_{i,j} = f_{j,i}

输入格式

输入是按以下格式从标准输入给出的。
N
f_{1,1} ... f_{1,N}
...
f_{N,1} ... f_{N,N}

输出格式

请将答案输出在一行内。

示例输入 1

3
0 2 3
2 0 -10
3 -10 0

示例输出 1

4
例如,x_1 = 1, x_2 = 1.5, x_3 = 4 ,猫1和2的幸福等级为2,猫3的幸福等级为0。

示例输入 2

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

示例输出 2

28