← 返回题目列表

Codeforces · 1154/D

D. 行走机器人

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

有一个机器人停留在 $$$Ox$$$ 轴上的 $$$X=0$$$ 处。他必须步行到$$$X=n$$$。你正在控制这个机器人并控制他的行走方式。该机器人有一个电池和一个带有太阳能电池板的蓄电池。

路径的第 $$$i$$$ 段(从 $$$X=i-1$$$ 到 $$$X=i$$$)可以暴露在阳光下,也可以不暴露在阳光下。数组 $$$s$$$ 表示哪些片段暴露在阳光下:如果片段 $$$i$$$ 暴露,则 $$$s_i = 1$$$,否则 $$$s_i = 0$$$。

机器人有一节容量为 $$$b$$$ 的电池和一个容量为 $$$a$$$ 的蓄电池。对于每个路段,您应该选择哪种类型的储能机器人将用于到达下一个点(可以是电池或蓄电池)。如果机器人继续使用电池,则电池的当前电量减一(如果电量为零,则机器人无法使用电池)。如果机器人继续使用蓄电池,则蓄电池的当前电量减一(如果电量为零,机器人也无法使用蓄电池)。

如果当前路段暴露在阳光下并且机器人使用电池穿过该路段,则蓄电池的电量会增加一(当然,其电量不能高于其最大容量)。

如果使用累加器通过某个段,则无论该段是否暴露,其电荷都会减1。

您知道步行到 $$$X=n$$$ 并不总是可能的。您希望您的机器人走得尽可能远。如果您对机器人进行最佳控制,请找出机器人可以通过的最大距离段数。

输入

输入的第一行包含三个整数 $$$n, b, a$$$ ($$$1 \le n, b, a \le 2 \cdot 10^5$$$) — 分别是机器人的目的地点、电池容量和蓄电池容量。

输入的第二行包含 $$$n$$$ 整数 $$$s_1, s_2, \dots, s_n$$$ ($$$0 \le s_i \le 1$$$),其中如果第 $$$i$$$ 段距离暴露在阳光下,则 $$$s_i$$$ 为 $$$1$$$,否则为 $$$0$$$。

输出

打印一个整数——如果你以最佳方式控制机器人,它可以通过的最大段数。

示例

输入 #1

5 2 1
0 1 0 1 0

输出 #1

5

输入 #2

6 2 1
1 0 0 1 0 1

输出 #2

3

注意

在第一个示例中,机器人可以使用蓄能器穿过第一段,并且电荷水平变为 $$$b=2$$$ 和 $$$a=0$$$。第二段可以使用电池通过,充电水平变为 $$$b=1$$$ 和 $$$a=1$$$。第三段可以使用累加器传递,并且电荷水平变为$$$b=1$$$和$$$a=0$$$。第四段可以使用电池通过,充电水平变为 $$$b=0$$$ 和 $$$a=1$$$。第五段可以使用累加器来传递。

在第二个示例中,机器人可以以任何顺序使用电池两次和蓄电池一次来完成最大数量的段。