English · Original
Chinese · Translation
Formal · Original
In a small restaurant there are _a_ tables for one person and _b_ tables for two persons.
It it known that _n_ groups of people come today, each consisting of one or two people.
If a group consist of one person, it is seated at a vacant one-seater table. If there are none of them, it is seated at a vacant two-seater table. If there are none of them, it is seated at a two-seater table occupied by single person. If there are still none of them, the restaurant denies service to this group.
If a group consist of two people, it is seated at a vacant two-seater table. If there are none of them, the restaurant denies service to this group.
You are given a chronological order of groups coming. You are to determine the total number of people the restaurant denies service to.
## Input
The first line contains three integers _n_, _a_ and _b_ (1 ≤ _n_ ≤ 2·105, 1 ≤ _a_, _b_ ≤ 2·105) — the number of groups coming to the restaurant, the number of one-seater and the number of two-seater tables.
The second line contains a sequence of integers _t_1, _t_2, ..., _t__n_ (1 ≤ _t__i_ ≤ 2) — the description of clients in chronological order. If _t__i_ is equal to one, then the _i_\-th group consists of one person, otherwise the _i_\-th group consists of two people.
## Output
Print the total number of people the restaurant denies service to.
[samples]
## Note
In the first example the first group consists of one person, it is seated at a vacant one-seater table. The next group occupies a whole two-seater table. The third group consists of one person, it occupies one place at the remaining two-seater table. The fourth group consists of one person, he is seated at the remaining seat at the two-seater table. Thus, all clients are served.
In the second example the first group consists of one person, it is seated at the vacant one-seater table. The next group consists of one person, it occupies one place at the two-seater table. It's impossible to seat the next group of two people, so the restaurant denies service to them. The fourth group consists of one person, he is seated at the remaining seat at the two-seater table. Thus, the restaurant denies service to 2 clients.
在一家小餐厅里，有 $a$ 张单人桌和 $b$ 张双人桌。
已知今天有 $n$ 组客人到来，每组由一人或两人组成。
如果一组仅有一人，他会坐在一张空的单人桌旁。如果没有空的单人桌，则坐在一张空的双人桌旁。如果也没有空的双人桌，则坐在一张已有一位顾客的双人桌旁的空位上。如果仍然没有这样的座位，餐厅将拒绝为该组提供服务。
如果一组有两人，他们会坐在一张空的双人桌旁。如果没有空的双人桌，餐厅将拒绝为该组提供服务。
你将获得客人到达的先后顺序。你需要计算餐厅拒绝服务的总人数。
第一行包含三个整数 $n$、$a$ 和 $b$（$1 ≤ n ≤ 2·10^5$，$1 ≤ a, b ≤ 2·10^5$）——分别表示前来餐厅的组数、单人桌数量和双人桌数量。
第二行包含一个整数序列 $t_1, t_2, ..., t_n$（$1 ≤ t_i ≤ 2$）——按时间顺序描述客人。如果 $t_i$ 等于 1，则第 $i$ 组由一人组成；否则，第 $i$ 组由两人组成。
请输出餐厅拒绝服务的总人数。
在第一个例子中，第一组由一人组成，他坐在一张空的单人桌旁。下一组占据了一整张双人桌。第三组由一人组成，他坐在剩余的那张双人桌的一个座位上。第四组由一人组成，他坐在该双人桌的剩余座位上。因此，所有顾客都被服务了。
在第二个例子中，第一组由一人组成，他坐在一张空的单人桌旁。下一组由一人组成，他坐在一张双人桌的一个座位上。下一组由两人组成，无法安排座位，因此餐厅拒绝服务。第四组由一人组成，他坐在该双人桌的剩余座位上。因此，餐厅拒绝了 $2$ 位顾客。
## Input
第一行包含三个整数 $n$、$a$ 和 $b$（$1 ≤ n ≤ 2·10^5$，$1 ≤ a, b ≤ 2·10^5$）——分别表示前来餐厅的组数、单人桌数量和双人桌数量。第二行包含一个整数序列 $t_1, t_2, ..., t_n$（$1 ≤ t_i ≤ 2$）——按时间顺序描述客人。如果 $t_i$ 等于 1，则第 $i$ 组由一人组成；否则，第 $i$ 组由两人组成。
## Output
请输出餐厅拒绝服务的总人数。
[samples]
## Note
在第一个例子中，第一组由一人组成，他坐在一张空的单人桌旁。下一组占据了一整张双人桌。第三组由一人组成，他坐在剩余的那张双人桌的一个座位上。第四组由一人组成，他坐在该双人桌的剩余座位上。因此，所有顾客都被服务了。在第二个例子中，第一组由一人组成，他坐在一张空的单人桌旁。下一组由一人组成，他坐在一张双人桌的一个座位上。下一组由两人组成，无法安排座位，因此餐厅拒绝服务。第四组由一人组成，他坐在该双人桌的剩余座位上。因此，餐厅拒绝了 $2$ 位顾客。
**Definitions**
Let $ n, a, b \in \mathbb{Z} $ denote the number of groups, one-seater tables, and two-seater tables, respectively.
Let $ T = (t_1, t_2, \dots, t_n) $ be a sequence where $ t_i \in \{1, 2\} $ represents the size of the $ i $-th group.
Let $ s_1 \in \mathbb{Z}_{\geq 0} $ denote the number of vacant one-seater tables.
Let $ s_2 \in \mathbb{Z}_{\geq 0} $ denote the number of vacant two-seater tables.
Let $ o_2 \in \mathbb{Z}_{\geq 0} $ denote the number of two-seater tables occupied by exactly one person.
Initialize:
$ s_1 = a $,
$ s_2 = b $,
$ o_2 = 0 $,
$ \text{denied} = 0 $.
**Constraints**
$ 1 \leq n \leq 2 \cdot 10^5 $,
$ 1 \leq a, b \leq 2 \cdot 10^5 $,
$ t_i \in \{1, 2\} $ for all $ i \in \{1, \dots, n\} $.
**Objective**
For each group $ i \in \{1, \dots, n\} $:
- If $ t_i = 1 $:
- If $ s_1 > 0 $: $ s_1 \gets s_1 - 1 $.
- Else if $ s_2 > 0 $: $ s_2 \gets s_2 - 1 $, $ o_2 \gets o_2 + 1 $.
- Else if $ o_2 > 0 $: $ o_2 \gets o_2 - 1 $.
- Else: $ \text{denied} \gets \text{denied} + 1 $.
- If $ t_i = 2 $:
- If $ s_2 > 0 $: $ s_2 \gets s_2 - 1 $.
- Else: $ \text{denied} \gets \text{denied} + 2 $.
Output $ \text{denied} $.
API Response (JSON)
{
"problem": {
"name": "A. Restaurant Tables",
"description": {
"content": "In a small restaurant there are _a_ tables for one person and _b_ tables for two persons. It it known that _n_ groups of people come today, each consisting of one or two people. If a group consist o",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF828A"
},
"statements": [
{
"statement_type": "Markdown",
"content": "In a small restaurant there are _a_ tables for one person and _b_ tables for two persons.\n\nIt it known that _n_ groups of people come today, each consisting of one or two people.\n\nIf a group consist o...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "在一家小餐厅里，有 $a$ 张单人桌和 $b$ 张双人桌。\n\n已知今天有 $n$ 组客人到来，每组由一人或两人组成。\n\n如果一组仅有一人，他会坐在一张空的单人桌旁。如果没有空的单人桌，则坐在一张空的双人桌旁。如果也没有空的双人桌，则坐在一张已有一位顾客的双人桌旁的空位上。如果仍然没有这样的座位，餐厅将拒绝为该组提供服务。\n\n如果一组有两人，他们会坐在一张空的双人桌旁。如果没有空的双人桌，餐厅将拒绝...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, a, b \\in \\mathbb{Z} $ denote the number of groups, one-seater tables, and two-seater tables, respectively. \nLet $ T = (t_1, t_2, \\dots, t_n) $ be a sequence where $ t_i \\in...",
"is_translate": false,
"language": "Formal"
}
]
}