/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は山を登っている。登山道は N 個の区間に分かれており、高橋君の現在の標高は最初 0 である。
i 番目の区間（ i = 1, 2, \ldots, N ）を通過すると、標高が D_i だけ変化する（ D_i が正なら上り、負なら下り、 0 なら平坦を意味する）。ただし、標高は常に 0 以上であり、変化後の標高が負になる場合は 0 になる。すなわち、通過前の標高を h とすると、通過後の標高は \max(h + D_i,\ 0) となる。
高橋君は体力を温存するために、登山の途中で ちょうど 1 回「ロープウェイ」を利用しなければならない。ロープウェイを利用すると、現在の標高 h が即座に \lfloor h / 2 \rfloor（ h を 2 で割って小数点以下を切り捨てた値）に変わる。
ロープウェイを利用できるタイミングは以下の N + 1 箇所のうちいずれか 1 つである：
- 1 番目の区間の前
- i 番目の区間と i+1 番目の区間の間（ i = 1, 2, \ldots, N-1 ）
- N 番目の区間の後
高橋君は、全 N 個の区間の通過およびロープウェイの利用をすべて終えた後の標高を最小化したい。最適なタイミングでロープウェイを利用したときの、最終的な標高の最小値を求めよ。
制約
- 1 \leq N \leq 5 \times 10^5
- -10^9 \leq D_i \leq 10^9
- 入力はすべて整数である。
入力
N D_1 D_2 \ldots D_N
- 1 行目には、区間の個数を表す整数 N が与えられる。
- 2 行目には、各区間での標高の変化量を表す N 個の整数 D_1, D_2, \ldots, D_N がスペース区切りで与えられる。
出力
最適なタイミングでロープウェイをちょうど 1 回利用したときの、最終的な標高の最小値を 1 行で出力せよ。
入力例 1
5 3 4 -2 5 -6
出力例 1
0
入力例 2
4 -5 10 -3 2
出力例 2
4
入力例 3
12 8 -3 15 -20 7 0 12 -5 -30 25 -4 6
出力例 3
13
入力例 4
30 100 -40 25 -200 300 -150 0 80 -30 60 -500 400 10 -20 35 -5 -5 90 -100 250 -60 70 -10 -400 500 -250 125 -75 30 -15
出力例 4
192
入力例 5
1 1000000000
出力例 5
500000000
Score : 400 pts
Problem Statement
Takahashi is climbing a mountain. The trail is divided into N sections, and Takahashi's current altitude is initially 0.
When passing through the i-th section (i = 1, 2, \ldots, N), the altitude changes by D_i (positive D_i means ascending, negative means descending, and 0 means flat). However, the altitude is always non-negative, and if the altitude after the change would be negative, it becomes 0. That is, if the altitude before passing is h, the altitude after passing becomes \max(h + D_i,\ 0).
To conserve his energy, Takahashi must use a ropeway exactly once during the climb. When using the ropeway, the current altitude h instantly changes to \lfloor h / 2 \rfloor (the value obtained by dividing h by 2 and rounding down).
The ropeway can be used at exactly one of the following N + 1 points:
- Before the 1st section
- Between the i-th section and the (i+1)-th section (i = 1, 2, \ldots, N-1)
- After the N-th section
Takahashi wants to minimize his altitude after completing all N sections and using the ropeway. Find the minimum possible final altitude when the ropeway is used at the optimal timing.
Constraints
- 1 \leq N \leq 5 \times 10^5
- -10^9 \leq D_i \leq 10^9
- All inputs are integers.
Input
N D_1 D_2 \ldots D_N
- The first line contains an integer N representing the number of sections.
- The second line contains N integers D_1, D_2, \ldots, D_N separated by spaces, representing the altitude change for each section.
Output
Print in one line the minimum possible final altitude when the ropeway is used exactly once at the optimal timing.
Sample Input 1
5 3 4 -2 5 -6
Sample Output 1
0
Sample Input 2
4 -5 10 -3 2
Sample Output 2
4
Sample Input 3
12 8 -3 15 -20 7 0 12 -5 -30 25 -4 6
Sample Output 3
13
Sample Input 4
30 100 -40 25 -200 300 -150 0 80 -30 60 -500 400 10 -20 35 -5 -5 90 -100 250 -60 70 -10 -400 500 -250 125 -75 30 -15
Sample Output 4
192
Sample Input 5
1 1000000000
Sample Output 5
500000000