#241. 干草堆

干草堆

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

奶牛们讨厌黑暗。

为了调整牛棚顶的电灯的亮度,Bessie必须建一座干草堆使得她能够爬上去够到灯泡。

一共有N\red {N}大包的干草(从1\red {1}N\red {N}编号)依靠传送带连续的传输进牛棚来。

i\red {i}包干草有一个宽度Wi\red {W_i}

所有的干草包的厚度和高度都为1\red {1}

Bessie必须利用所有N\red {N}包干草来建立起干草堆。

她可以想放多少包就放多少包来建立起草堆的地基(当然是紧紧的放在一行中)。

接下来她可以将下一个草包放在之前一级的上方来建立新的一级。

输入格式

1\red 1行:一个整数N\red {N}

2..N+1\red {2..N+1}行:第i+1\red {i+1}行包含整数Wi\red {W_i}

输出格式

输出一个整数,表示草包堆的最高的高度。

样例

输入样例

3
1
2
3

输出样例

2

提示

1N100000\red {1≤N≤100000},

1Wi10000\red {1≤W_i ≤10000}

注意:每一级不能比下面的一级宽。

她持续的这么放置,直到所有的草包都被安置完成。

她必须按照草包进入牛棚的顺序堆放草包。

说得更清楚一些:一旦她将一个草包放在第二级 ,那么她不能将接下来的草包放在第一级上。

Bessie的目标是建立起最高的草包堆。

国庆s组2

未参加
状态
已结束
规则
OI
题目
4
开始于
2021-10-6 17:00
结束于
2021-10-6 23:00
持续时间
6 小时
主持人
参赛人数
5