#6399. yww 与魔法阵

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: yww

题目描述

2100年,yww在地球的某个角落发现了一个魔法阵。这个魔法阵包含很多魔法水晶,这些魔法水晶呈三角形状排布,一共有 n 行,第 i 行有 i 个。这些魔法水晶都储存了巨大的能量,可惜有一些魔法水晶被破坏了。

2200年,外星人入侵地球。你,作为地球军团的总司令,必须消灭这些外星人。你决定激活这个魔法阵。你可以激活一些魔法水晶,要求这些魔法水晶构成一个三角形(不能有突出来的部分,中间是空的)。这些魔法水晶会修复内部的魔法水晶并激活内部的魔法水晶。最终这个小魔法阵的威力就是被激发的魔法水晶数目。为了让威力最大化,三角形必须是正着放的。

因为你要保卫地球,所以你必须选择威力最大的小魔法阵。

请你计算小魔法阵的威力的最大值。如果不能选择任何魔法水晶就输出 0

输入格式

第一行有一个整数 n

接下来 n 行,第 i 行有 i 个整数,第 j 个数 a_{i,j} 表示三角形第 i 行第 j 个魔法水晶的状态, 1 表示已损坏, 0 表示未损坏。

输出格式

一个整数:答案。

样例

样例一

input

2
0
1 0

output

1

explanation

随便选择一个未损坏的魔法水晶即可。

样例二

input

5
0
0 0
0 0 1
0 1 0 0
0 0 0 0 1

output

10

explanation

(2,1),(3,1),(3,2),(4,1),(4,3),(5,1),(5,2),(5,3),(5,4) 即可。

数据范围与提示

本题输入量较大,建议使用快速的读入方式。

子任务 1 10 分): n\leq 5

子任务 2 10 分): n\leq 50

子任务 3 10 分): n\leq 200

子任务 4 20 分): n\leq 1000

~~子任务 4.5 20 分): n\leq 5000 ,数据随机,每个水晶有 50\% 的概率未损坏, 50\% 的概率已损坏。~~由于数据太大,这个子任务被删除了。

子任务 5 50 分): n\leq 5000

对于 100\% 的数据, 1\leq n\leq 5000,a_{i,j}\in\{0,1\}

题目来源:全是水题的GDOI模拟赛 by yww