C. Convert to Ones

Codeforces

IDCF998C

Time1000ms

Memory256MB

Difficulty—

math

English · Original

Chinese · Translation

Formal · Original

You've got a string $a_1, a_2, \dots, a_n$, consisting of zeros and ones. Let's call a sequence of consecutive elements $a_i, a_{i + 1}, \ldots, a_j$ ($1\leq i\leq j\leq n$) a _substring_ of string $a$. You can apply the following operations any number of times: * Choose some substring of string $a$ (for example, you can choose entire string) and reverse it, paying $x$ coins for it (for example, «_0101101_» $\to$ «_0111001_»); * Choose some substring of string $a$ (for example, you can choose entire string or just one symbol) and replace each symbol to the opposite one (zeros are replaced by ones, and ones — by zeros), paying $y$ coins for it (for example, «_0101101_» $\to$ «_0110001_»). You can apply these operations in any order. It is allowed to apply the operations multiple times to the same substring. What is the minimum number of coins you need to spend to get a string consisting only of ones? ## Input The first line of input contains integers $n$, $x$ and $y$ ($1 \leq n \leq 300\,000, 0 \leq x, y \leq 10^9$) — length of the string, cost of the first operation (substring reverse) and cost of the second operation (inverting all elements of substring). The second line contains the string $a$ of length $n$, consisting of zeros and ones. ## Output Print a single integer — the minimum total cost of operations you need to spend to get a string consisting only of ones. Print $0$, if you do not need to perform any operations. [samples] ## Note In the first sample, at first you need to reverse substring $[1 \dots 2]$, and then you need to invert substring $[2 \dots 5]$. Then the string was changed as follows: «_01000_» $\to$ «_10000_» $\to$ «_11111_». The total cost of operations is $1 + 10 = 11$. In the second sample, at first you need to invert substring $[1 \dots 1]$, and then you need to invert substring $[3 \dots 5]$. Then the string was changed as follows: «_01000_» $\to$ «_11000_» $\to$ «_11111_». The overall cost is $1 + 1 = 2$. In the third example, string already consists only of ones, so the answer is $0$.

你有一个由零和一组成的字符串 $a_1, a_2, dots.h, a_n$。我们将连续元素序列 $a_i, a_(i + 1), dots.h, a_j$（$1 lt.eq i lt.eq j lt.eq n$）称为字符串 $a$ 的一个 _子串_。你可以任意次数地应用以下操作：你可以按任意顺序应用这些操作，允许对同一个子串多次应用操作。你需要花费最少多少枚硬币，才能得到一个仅由一组成的字符串？输入的第一行包含整数 $n$, $x$ 和 $y$（$1 lt.eq n lt.eq 300 thin 000$, $0 lt.eq x, y lt.eq 10^9$）——字符串长度、第一种操作（子串反转）的代价和第二种操作（子串中所有元素取反）的代价。第二行包含一个长度为 $n$ 的字符串 $a$，由零和一组成。请输出一个整数——为得到仅由一组成的字符串所需花费的最小总代价。如果无需执行任何操作，请输出 $0$。在第一个样例中，你首先需要反转子串 $[ 1 dots.h 2 ]$，然后需要对子串 $[ 2 dots.h 5 ]$ 取反。字符串变化如下： «_01000_» $arrow.r$ «_10000_» $arrow.r$ «_11111_»。操作总代价为 $1 + 10 = 11$。在第二个样例中，你首先需要对子串 $[ 1 dots.h 1 ]$ 取反，然后对子串 $[ 3 dots.h 5 ]$ 取反。字符串变化如下： «_01000_» $arrow.r$ «_11000_» $arrow.r$ «_11111_»。总代价为 $1 + 1 = 2$。在第三个样例中，字符串已经仅由一组成，因此答案为 $0$。 ## Input 输入的第一行包含整数 $n$, $x$ 和 $y$（$1 lt.eq n lt.eq 300 thin 000$, $0 lt.eq x, y lt.eq 10^9$）——字符串长度、第一种操作（子串反转）的代价和第二种操作（子串中所有元素取反）的代价。第二行包含一个长度为 $n$ 的字符串 $a$，由零和一组成。 ## Output 请输出一个整数——为得到仅由一组成的字符串所需花费的最小总代价。如果无需执行任何操作，请输出 $0$。 [samples] ## Note 在第一个样例中，你首先需要反转子串 $[ 1 dots.h 2 ]$，然后需要对子串 $[ 2 dots.h 5 ]$ 取反。字符串变化如下：«_01000_» $arrow.r$ «_10000_» $arrow.r$ «_11111_»。操作总代价为 $1 + 10 = 11$。在第二个样例中，你首先需要对子串 $[ 1 dots.h 1 ]$ 取反，然后对子串 $[ 3 dots.h 5 ]$ 取反。字符串变化如下：«_01000_» $arrow.r$ «_11000_» $arrow.r$ «_11111_»。总代价为 $1 + 1 = 2$。在第三个样例中，字符串已经仅由一组成，因此答案为 $0$。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of the binary string. Let $ x, y \in \mathbb{Z}_{\geq 0} $ be the costs of reverse and invert operations, respectively. Let $ a = (a_1, a_2, \dots, a_n) \in \{0,1\}^n $ be the input binary string. Let a *segment* be a maximal contiguous substring of zeros. Let $ k $ be the number of such zero-segments in $ a $. **Constraints** 1. $ 1 \leq n \leq 300{,}000 $ 2. $ 0 \leq x, y \leq 10^9 $ 3. Each $ a_i \in \{0,1\} $ **Objective** Find the minimum cost to convert $ a $ to the all-ones string using any number of: - **Reverse** operation on any substring: cost $ x $ - **Invert** operation on any substring: cost $ y $ **Key Insight** The reverse operation does not change the number of zero-segments. The invert operation on a substring containing zero-segments can merge or eliminate them. To eliminate all zeros: - Each zero-segment must be inverted at least once. - Reverse operations can be used to merge adjacent zero-segments, reducing the number of invert operations needed. **Optimal Strategy** - If $ k = 0 $, cost = 0. - Otherwise, we can: - **Option 1**: Invert each zero-segment individually: cost = $ k \cdot y $ - **Option 2**: Use reverse operations to merge all zero-segments into one, then invert once: cost = $ (k - 1) \cdot x + y $ **Objective Function** $$ \min\left( k \cdot y,\ (k - 1) \cdot x + y \right) $$ if $ k > 0 $; otherwise $ 0 $.

Samples

Input #1

5 1 10
01000

Output #1

Input #2

5 10 1
01000

Output #2

Input #3

7 2 3
1111111

Output #3

API Response (JSON)

{
  "problem": {
    "name": "C. Convert to Ones",
    "description": {
      "content": "You've got a string $a_1, a_2, \\dots, a_n$, consisting of zeros and ones. Let's call a sequence of consecutive elements $a_i, a_{i + 1}, \\ldots, a_j$ ($1\\leq i\\leq j\\leq n$) a _substring_ of string $",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF998C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You've got a string $a_1, a_2, \\dots, a_n$, consisting of zeros and ones.\n\nLet's call a sequence of consecutive elements $a_i, a_{i + 1}, \\ldots, a_j$ ($1\\leq i\\leq j\\leq n$) a _substring_ of string $...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你有一个由零和一组成的字符串 $a_1, a_2, dots.h, a_n$。\n\n我们将连续元素序列 $a_i, a_(i  +  1), dots.h,  a_j$（$1 lt.eq  i lt.eq  j lt.eq  n$）称为字符串 $a$ 的一个 _子串_。\n\n你可以任意次数地应用以下操作：\n\n你可以按任意顺序应用这些操作，允许对同一个子串多次应用操作。\n\n你需要花费最少多少枚硬币，才能...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the binary string.  \nLet $ x, y \\in \\mathbb{Z}_{\\geq 0} $ be the costs of reverse and invert operations, respectively.  \nLet $ a = (a_1, a...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments