← 返回题目列表

AtCoder · awc0096_d

D. 徒步旅行和休息

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

高桥正在爬山。路线分为 N 部分,高桥当前的高度最初是 0.

当经过 i- 第节 (i = 1, 2, \ldots, N),高度变化 D_i (正 D_i 表示升序,负数表示降序, 0 表示平坦)。但是,海拔高度始终为非负值,如果改变后的海拔高度为负值,则变为 0。也就是说,如果经过之前的高度是 h,经过后的海拔高度变为 \max(h + D_i,\ 0).

为了保存能量,高桥必须使用 索道正好一次 攀爬期间。使用索道时,当前海拔高度 h 立即更改为 \lfloor h / 2 \rfloor (除以得到的值 h by 2 并向下舍入)。

索道可在以下任一地点使用 N + 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
  • 第一行包含一个整数 N 代表节数。
  • 第二行包含 N 整数 D_1, D_2, \ldots, D_N 以空格分隔,代表每个部分的海拔高度变化。

输出

在一行中打印索道在最佳时间仅使用一次时可能的最小最终高度。


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