#2758. 「JOI 2014 Final」年轮蛋糕

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

题目描述

译自 JOI 2014 Final T3「バームクーヘン

JOI 君马上要和妹妹 JOI 子和 JOI 美一起吃小吃。今天的小吃是他们三个人都很喜欢的年轮蛋糕。

年轮蛋糕是像下图一样呈圆筒形的蛋糕。为了把蛋糕分给三个人,JOI 君必须沿着半径方向切 3 刀,从而把蛋糕分成三块。然而,由于年轮蛋糕硬得像实木一样,要让刀切进去并不简单。因此,这个年轮蛋糕上事先准备了 N 个切口,而 JOI 君只能在有切口的位置下刀。切口按顺时针顺序编号为 1 N ,对于 1\le i\le N-1 ,第 i 个切口和第 i+1 个切口之间部分的大小是 A_{i} 。第 N 个切口和第 1 个切口之间部分的大小是 A_{N}

Baumkuchen1.png

图 1:一个年轮蛋糕的例子,$N=6,A_{1}=1,A_{2}=5,A_{3}=4,A_{4}=5,A_{5}=2,A_{6}=4$

妹控的 JOI 君在把蛋糕切成 3 块之后,自己选走最小的一块吃掉,把剩下两块分给两个妹妹。而另一方面,JOI 君太喜欢年轮蛋糕了,只要能吃到的时候就会想吃很多很多。试求:JOI 君吃掉的蛋糕的大小至多不超过多少。

给出切口个数 N 和表示各部分大小的整数 A_{1},\cdots ,A_{N} ,请求出把年轮蛋糕切成 3 块之后最小一块大小的最大值。

输入格式

1 行有一个整数 N ,表示年轮蛋糕上有 N 个切口; 接下来有 N 行,第 i(1\le i\le N) 行有一个整数 A_{i} ,表示第 i 个切口和第 i+1 个切口之间部分(当 i=N 时即为第 N 个和第 1 个之间部分)的大小。

输出格式

输出一行,一个整数,表示当把年轮蛋糕切成 3 块之后最小块大小的最大值。

样例

输入样例 1

6
1
5
4
5
2
4

输出样例 1

6

样例说明 1

Baumkuchen2.png

图 2:从第 $1,3,5$ 个切口下刀时是最优解(即图中粗实线位置)。

输入样例 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

数据范围与提示

全部的输入数据满足:

  • 3\le N\le 100000
  • 1\le A_{i}\le 10^{9}

子任务 1( 5 分)

满足 N\le 100

子任务 2( 15 分)

满足 N\le 400

子任务 3( 30 分)

满足 N\le 8000

子任务 4( 50 分)

没有额外限制。