Problem G
Fireworks
The audience especially likes when both a green and a red firework explode simultaneously, this is called an awesome combination, AC for short.
You would like to maximize the number of ACs in your show.
Some firework positions are already occupied with red or green fireworks, while other positions are up to you to decide among your extra $R$ red fireworks and $G$ green fireworks.
Input
The first line contains three integers $N$, $R$, and $G$ ($2 \leq N \leq 50,000$, $0 \leq R, G \leq 50,000$), where $N$ is the number of fireworks positions, $R$ and $G$ are the number of extra red and green fireworks respectively.
The second line contains $N$ characters each of which is one of ‘R’, ‘G’, or ‘X’, representing how the firework positions are originally assigned. Here, ‘R’ means that the firework is red, ‘G’ means it is green, and ‘X’ means that you need to place a firework at that position.
The number of positions where you need to place a firework does not exceed $R + G$
Output
A single integer. The maximum number of ACs you can create in your show.
Scoring
|
Group |
Points |
Constraints |
|
$1$ |
$15$ |
$N \leq 2000$ and $R=G=0$ |
|
$2$ |
$20$ |
$N \leq 2000$ |
|
$3$ |
$30$ |
$N \leq 50\, 000$ and $R=G=0$ |
|
$4$ |
$35$ |
$N \leq 50\, 000$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
7 2 1 GGRXRXX |
3 |
