997A.md (2434B)
1 Source: https://codeforces.com/problemset/problem/997/A 2 3 A. Convert to Ones 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You've got a string $a_1, a_2, \dots, a_n$, consisting of zeros and ones. 22 23 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$. 24 25 You can apply the following operations any number of times: 26 27 * 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»); 28 * 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»). 29 30 You can apply these operations in any order. It is allowed to apply the operations multiple times to the same substring. 31 32 What is the minimum number of coins you need to spend to get a string consisting only of ones? 33 34 Input 35 36 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). 37 38 The second line contains the string $a$ of length $n$, consisting of zeros and ones. 39 40 Output 41 42 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. 43 44 Examples 45 46 Input 47 48 ``` 49 5 1 10 50 01000 51 ``` 52 53 Output 54 55 ``` 56 11 57 ``` 58 59 Input 60 61 ``` 62 5 10 1 63 01000 64 ``` 65 66 Output 67 68 ``` 69 2 70 ``` 71 72 Input 73 74 ``` 75 7 2 3 76 1111111 77 ``` 78 79 Output 80 81 ``` 82 0 83 ``` 84 85 Note 86 87 In the first sample, at first you need to reverse substring $[1 \dots 2]$, and then you need to invert substring $[2 \dots 5]$. 88 89 Then the string was changed as follows: 90 91 «01000» $\to$ «10000» $\to$ «11111». 92 93 The total cost of operations is $1 + 10 = 11$. 94 95 In the second sample, at first you need to invert substring $[1 \dots 1]$, and then you need to invert substring $[3 \dots 5]$. 96 97 Then the string was changed as follows: 98 99 «01000» $\to$ «11000» $\to$ «11111». 100 101 The overall cost is $1 + 1 = 2$. 102 103 In the third example, string already consists only of ones, so the answer is $0$.