Problem 6D. 桌游

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

Problem 6D. 桌游

时间限制:1s

空间限制:128MB

题目描述

如你所见,最近\(lhy\)由于七圣召唤而沉迷于桌游。现在,他的桌上有\(n\)张卡牌上下叠成一堆,编号1~n,卡牌有行动牌和技能牌两种。每张技能牌都会有一个伤害值\(a_i \ne 0\),方便起见,行动牌的伤害值\(a_i=0\).
每次\(lhy\)可以从牌堆顶部获取一张牌,如果这是一张技能牌,那么\(lhy\)可以选择弃置之,亦可将其置于手牌区顶部;
如果获得的是一张行动牌,那么直接弃置这张牌,然后\(lhy\)可以选择将手牌区顶部的牌弃置(如果有的话),并造成\(a_i\)点伤害,也可以选择直接跳过。
现在你看到了整个牌堆,请问\(lhy\)最多可以打出多少伤害。

数据格式

输入

第一行,一个正整数\(n\),表示牌的数量。
第二行,\(n\)个非负整数,表示牌的伤害值,如果\(a_i=0\),它是行动牌,否则,它是技能牌。

输出

一个非负整数,表示最大的伤害。

样例

输入1

5
3 3 3 0 0

输出1

6

输入2

6
0 3 3 0 0 3

输出2

6

输入3

7
1 2 5 0 4 3 0

输出3

9

数据范围及约定

\(1 \le n \le 10^5\).

2023秋 悬赏令第六周

未参加
状态
已结束
规则
OI
题目
6
开始于
2023-11-12 18:30
结束于
2023-11-19 00:00
持续时间
149.5 小时
主持人
参赛人数
58