[ABC102D] Equal Cut
题意翻译
给定一个序列。要求把这个序列分成连续的四份,记这四份内数字和分别为 $a,b,c,d$ ,最小化 $a,b,c,d$ 的极差。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc102/tasks/arc100_b
すぬけ君は、長さ $ 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 $ の最大値と最小値の差の絶対値としてあり得る最も小さい値を求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $
输出格式
$ P,Q,R,S $ の最大値と最小値の差の絶対値としてあり得る最も小さい値を出力せよ。
输入输出样例
输入样例 #1
5
3 2 4 1 2
输出样例 #1
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
说明
### 制約
- $ 4\ \leq\ N\ \leq\ 2\ \times\ 10^5 $
- $ 1\ \leq\ A_i\ \leq\ 10^9 $
- 入力はすべて整数である。
### Sample Explanation 1
$ 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 $ が答えになります。