/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
すぬけ君は、長さ N の整数列 A を持っています。
すぬけ君は A を 3 箇所で切って、4 つの（空でない）連続する部分列 B,C,D,E に分解します。 切る位置は自由に選ぶことができます。
ここで、整数列 B,C,D,E について、その要素の総和をそれぞれ P,Q,R,S とおきます。 すぬけ君は、P,Q,R,S の最大値と最小値の差の絶対値が小さいほど嬉しいです。 P,Q,R,S の最大値と最小値の差の絶対値としてあり得る最も小さい値を求めてください。
制約
- 4 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N
出力
P,Q,R,S の最大値と最小値の差の絶対値としてあり得る最も小さい値を出力せよ。
入力例 1
5 3 2 4 1 2
出力例 1
2
B,C,D,E=(3),(2),(4),(1,2) と分割すれば、P=3,Q=2,R=4,S=1+2=3 となります。 このとき、P,Q,R,S の最大値は 4、最小値は 2 で、その差の絶対値は 2 です。 最大値と最小値の差の絶対値を 2 未満にすることは出来ないため、2 が答えになります。
入力例 2
10 10 71 84 33 6 47 23 25 52 64
出力例 2
36
入力例 3
7 1 2 3 1000000000 4 5 6
出力例 3
999999994
Score : 600 points
Problem Statement
Snuke has an integer sequence A of length N.
He will make three cuts in A and divide it into four (non-empty) contiguous subsequences B, C, D and E. The positions of the cuts can be freely chosen.
Let P,Q,R,S be the sums of the elements in B,C,D,E, respectively. Snuke is happier when the absolute difference of the maximum and the minimum among P,Q,R,S is smaller. Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.
Constraints
- 4 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 ... A_N
Output
Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.
Sample Input 1
5 3 2 4 1 2
Sample Output 1
2
If we divide A as B,C,D,E=(3),(2),(4),(1,2), then P=3,Q=2,R=4,S=1+2=3. Here, the maximum and the minimum among P,Q,R,S are 4 and 2, with the absolute difference of 2. We cannot make the absolute difference of the maximum and the minimum less than 2, so the answer is 2.
Sample Input 2
10 10 71 84 33 6 47 23 25 52 64
Sample Output 2
36
Sample Input 3
7 1 2 3 1000000000 4 5 6
Sample Output 3
999999994