← 返回题目列表

AtCoder · icpc2013summer_day2_b

B. 疏散路线

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

日本积极开展防灾研究,近年来其重要性不断增加。 疏散路线的评估也是一个重要的研究领域。 这次我们来评估一下直道的安全性。

该段落是 从一端的单元到另一端的单元,分为 W 个单元。 它的编号为 1,  2,  3,  … ,  W 。 通道中的每个单元都有以下门之一:入口门、出口门或防火门。 一条通道内可以有多个入口门、出口门和防火门。

在这个问题中,时间 假设 t=0 发生火灾。 因此,在通道外试图疏散的人们会从入口门进入通道,并试图从出口门逃生到更安全的地方。 每个被疏散的人每单位时间可以移动一个单位或留在当前单位。 换句话说,时间 t 中的一个人是一个单位 当一个人处于 i 时,时间 t+1 单位 三个数字中的 i-1,  i,   i+1 三个数字中 1 以上 W 您可以选择以下内容并移动到具有该编号的单位。 设有防火门的单位在一定时间后会完全关闭,使疏散人员无法进入单位。此外,该单位的人员将无法从该单位转移到其他单位。

该问题的目的是根据每扇门的信息,计算在疏散人员表现最佳的情况下能够到达出口门的最大人数。

通道信息 它由W整数a_i给出。 当

  • a_i = 0时, 表示第i 个单元是出口门。
  • a_i < 0时, 表示第i 该装置由防火门启动。 |a_i| 表示您将无法再进入或退出。
  • a_i > 0时, 表示第i 表示单位为入户门,时间 每个 t=0, 1, 2, … , a_i-1 中只有一个人 出现在第 i 个单位中。时间 出现在 t 的人是 从 t+1 开始移动。
请注意,一个单位中可能有多人。

找出能够到达出口的最大人数。

入力形式

输入按以下格式给出

W
a_1 a_2 ... a_W

出力形式

输出一行中的最大人数。

制約

  • 1 ≤ W ≤ 10^5
  • |a_i|   ≤ 10^4
  • 所有输入值都是整数。 第

入出力例

入力例 1

7
2 0 -2 3 2 -2 0

出力例 1

4

1,   4,   5个单元有一个入口门, 第 2,   6单元有一个出口门。 从第
1单元开始,2单位中可以出现两个人。 一个人可以前往第
4单元开始,2个单位。
5单元开始,7个单位。
因此,总共有四个人可以到达出口。

入力例 2

4
1 1 1 1

出力例 2

0

没有人可以逃脱,因为没有出口。

入力例 3

9
10 -10 10 -10 10 -10 10 -10 0

出力例 3

24