Poisonous Full-Course

题目描述

Takahashi 决定在一家餐馆享用由 $N$ 道菜组成的精心设计的全套餐点。
第 $i$ 道菜为：

如果 $X_i=0$，则为一份具有美味值 $Y_i$ 的 解毒 菜； 如果 $X_i=1$，则为一份具有美味值 $Y_i$ 的 有毒 菜。

当 Takahashi 吃一道菜时，他的状态按如下变化：

最初，Takahashi 有一个健康的胃。 当他有一个 健康的胃 时， 如果他吃了一道 解毒 菜，他的胃将 保持健康； 如果他吃了一道 有毒 菜，他将 胃部不适。

当他有一个 胃部不适 时， 如果他吃了一道 解毒 菜，他的胃将 变为健康； 如果他吃了一道 有毒 菜，他将 死亡。

用餐按如下进行。

按顺序对 $i = 1, \ldots, N$ 重复以下过程。 首先，第 $i$ 道菜被端给 Takahashi。 接着，他选择“吃”或“跳过”该道菜。 如果他选择“吃”，他吃下第 $i$ 道菜。他的状态也会根据所吃的菜发生变化。 如果他选择“跳过”，他不吃第 $i$ 道菜。该道菜不能在之后再端上或以其他方式保留。

最后，（如果他的状态发生变化，则在变化之后）如果他没有死， 如果 $i \neq N$，他继续到下一道菜。 如果 $i = N$，他活着走出餐馆。

重要的会议在等着他，所以他必须活着走出去。
当他在此条件下决定是否“吃”或“跳过”这些菜时，求他所吃的菜的美味值之和的最大可能值（如果他什么都不吃则为 $0$）。

输入格式

输入由标准输入给出，格式如下： $N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$

输出格式

以整数形式输出答案。

5
1 100
1 300
0 -200
1 500
1 300

600

4
0 -1
1 -2
0 -3
1 -4

0

15
1 900000000
0 600000000
1 -300000000
0 -700000000
1 200000000
1 300000000
0 -600000000
1 -900000000
1 600000000
1 -100000000
1 -400000000
0 900000000
0 200000000
1 -500000000
1 900000000

4100000000

提示

所有输入值均为整数。 $1 \le N \le 3 \times 10^5$ $X_i \in \{0,1\}$ 换言之，$X_i$ 要么为 $0$ 要么为 $1$。

$-10^9 \le Y_i \le 10^9$下面的选择使他所吃的菜的美味值总和为 $600$，这是可能的最大值。

他跳过第 $1$ 道菜。 现在他的胃是健康的。 他吃第 $2$ 道菜。 现在他胃部不适，且他所吃的菜的美味值总和为 $300$。 他吃第 $3$ 道菜。 现在他的胃再次健康，且他所吃的菜的美味值总和为 $100$。 他吃第 $4$ 道菜。 现在他胃部不适，且他所吃的菜的美味值总和为 $600$。 他跳过第 $5$ 道菜。 现在他仍然胃部不适。 最后，他没有死亡，因此他活着走出餐馆。
对于此输入，最优策略是什么都不吃，此时答案为 $0$。
答案可能不能适合 32 位整型。

标签: AtCoder|abc306D

来源

AtCoder|abc306D