问题4396--充电机器人

4396: 充电机器人

时间限制: 1 Sec  内存限制: 512 MB
提交: 0  解决: 0
[提交] [状态] [讨论版] [命题人:]

题目描述

There is a robot staying at X=0 on the Ox axis. He has to walk to X=n. You are controlling this robot and controlling how he goes. The robot has a battery and an accumulator with a solar panel. The i-th segment of the path (from X=i1 to X=i) can be exposed to sunlight or not. The array s denotes which segments are exposed to sunlight: if segment i is exposed, then si=1, otherwise si=0. The robot has one battery of capacity b and one accumulator of capacity a. For each segment, you should choose which type of energy storage robot will use to go to the next point (it can be either battery or accumulator). If the robot goes using the battery, the current charge of the battery is decreased by one (the robot can't use the battery if its charge is zero). And if the robot goes using the accumulator, the current charge of the accumulator is decreased by one (and the robot also can't use the accumulator if its charge is zero). If the current segment is exposed to sunlight and the robot goes through it using the battery, the charge of the accumulator increases by one (of course, its charge can't become higher than it's maximum capacity). If accumulator is used to pass some segment, its charge decreases by 1 no matter if the segment is exposed or not. You understand that it is not always possible to walk to X=n. You want your robot to go as far as possible. Find the maximum number of segments of distance the robot can pass if you control him optimally. 在一个数轴上,有一个机器人要从 x = 0 处移动到 x = n 处。机器人身上有两种电池,第一种是普通电池,第二种是太阳能可充电电池,普通电池的容量上限为b 点电量,太阳能电池的容量上限为 a 点电量。 定义数轴上的第 i 段线段代表左端点为 x = i - 1,右端点为 x = i 的线段。 这 n 条线段中,有一些线段可以被太阳照射到。 当机器人向右移动一个单位时,它会消耗一点电量。 当机器人走到一个可以被太阳照射到的线段上时,如果他是使用普通电池走到这条线段的并且太阳能电池的电量不满,则可以增加一点电量。这里的线段特指长度为 1 的线段。即如果它从一条被照射到的线段上走到另一条被照射的线段上,依然有可能增加电量。使用太能能电池在移动的时候不可以同时充电。 机器人总电量为 0 或到达终点时会停下。现在请你求出机器人最远可以走多远。

输入

The first line of the input contains three integers n,b,a (1≤n,b,a≤2*10^5) — the robot's destination point, the battery capacity and the accumulator capacity, respectively. The second line of the input contains n integers s1,s2,…,sn (0≤si≤1), where si is 1 if the i-th segment of distance is exposed to sunlight, and 0 otherwise. 第一行三个整数代表 n, b, a 下面一行 n 个整数,第 i 个整数 s_i描述第 i 条线段是否被阳光照射,如果被照射则为 1,否则为 0。

输出

Print one integer — the maximum number of segments the robot can pass if you control him optimally.

样例输入

(1)
5 2 1
0 1 0 1 0



(2)
6 2 1
1 0 0 1 0 1

样例输出

(1)
5


(2)
3

In the first example the robot can go through the first segment using the accumulator, and charge levels become b=2 and a=0. The second segment can be passed using the battery, and charge levels become b=1 and a=1. The third segment can be passed using the accumulator, and charge levels become b=1 and a=0. The fourth segment can be passed using the battery, and charge levels become b=0 and a=1. And the fifth segment can be passed using the accumulator.

In the second example the robot can go through the maximum number of segments using battery two times and accumulator one time in any order.

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

在第二个示例中,机器人可以使用电池两次遍历最大数量的段,并以任意顺序一次遍历蓄电池。

来源/分类

 

[提交] [状态]