Type: Default 1000ms 256MiB

跳跳跳

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Mibbp正在玩一个游戏。游戏中有 N+1座建筑—从 0 到 N编号,从左到右排列。

编号为 0的建筑高度为 0 个单位,编号为 i 的建筑高度为 H(i)个单位。起初,机器人在编号为 0的建筑处。每一步,它跳到下一个(右边)建筑。假设机器人在第 k 个建筑,且它现在的能量值是 E,下一步它将跳到第 k+1个建筑。如果 H(k+1)>E,那么机器人就失去 H(k+1)−E 的能量值,否则它将得到 EH(k+1) 的能量值。游戏目标是到达第 N个建筑,在这个过程中能量值不能为负数个单位。

现在的问题是机器人至少以多少能量值开始游戏,才可以保证成功完成游戏?

输入格式

第一行输入整数 N

第二行是 N个空格分隔的整数,H(1),H(2),…,H(N) 代表建筑物的高度。

输出格式

输出一个整数,表示所需的最少单位的初始能量值上取整后的结果。

数据范围

1≤N,H(i)≤105{10^5},

5
3 4 3 2 4
4
3
4 4 4
4
3
1 6 4
3

二分训练

Not Claimed
Status
Done
Problem
11
Open Since
2022-11-29 19:00
Deadline
2022-12-5 0:00
Extension
24 hour(s)