codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.