/ Vijos / 题库 /

セチの祈り

セチの祈り

背景

琼花飘落 彩蝶曼舞 又是一年春
满腹愁情 化作伤春酒
梧桐细雨 影影绰绰 残阳落
韶华飞逝 梦断都成空

描述

在 Ninian 的花园里,有许多琼花,环绕着中间的凉亭。
有 N 片琼花,组成一个环。
Ninian 想在凉亭中发动 [セチの祈り] , 需要划分出三个区域的琼花,为了平均,要最大化面积最小的区域的面积。

划分区域:即用三刀把这个环分成三段,每段称之为一个区域。

格式

输入格式

第一行一个整数 N 。
接下来 N 个整数 Si ,表示第 i 片琼花的面积。

输出格式

输出一个整数,面积最小的区域的面积。

样例1

样例输入1

6
1
5
4
5
2
4

样例输出1

6

样例2

样例输入2

30
1
34
44
13
30
1
9
3
7
7
20
12
2
44
6
9
44
31
17
20
33
18
48
23
19
31
24
50
43
15

样例输出2

213

限制

对于 20% 的数据:
3 ≤ N ≤ 400

对于 100% 的数据:
3 ≤ N ≤ 100 000
1 ≤ Ai ≤ 1 000 000 000

来源

布吉岛。

信息

ID
1894
难度
7
分类
(无)
标签
(无)
递交数
557
已通过
96
通过率
17%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

Deplore NOIP模拟赛