Grime Zoo
Contest: Technocup 2021 - Elimination Round 3
Difficulty rating: 2100
Tags: brute force, greedy, implementation, strings

Currently, XXOC's rap is a string consisting of zeroes, ones, and question marks. Unfortunately, haters gonna hate. They will write $$$x$$$ angry comments for every occurrence of subsequence 01 and $$$y$$$ angry comments for every occurrence of subsequence 10. You should replace all the question marks with 0 or 1 in such a way that the number of angry comments would be as small as possible.

String $$$b$$$ is a subsequence of string $$$a$$$, if it can be obtained by removing some characters from $$$a$$$. Two occurrences of a subsequence are considered distinct if sets of positions of remaining characters are distinct.

Input format:
The first line contains string $$$s$$$ — XXOC's rap ($$$1 \le |s| \leq 10^5$$$). The second line contains two integers $$$x$$$ and $$$y$$$ — the number of angry comments XXOC will recieve for every occurrence of 01 and 10 accordingly ($$$0 \leq x, y \leq 10^6$$$).

Output format:
Output a single integer — the minimum number of angry comments.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example one of the optimum ways to replace is 001. Then there will be $$$2$$$ subsequences 01 and $$$0$$$ subsequences 10. Total number of angry comments will be equal to $$$2 \cdot 2 + 0 \cdot 3 = 4$$$.

In the second example one of the optimum ways to replace is 11111. Then there will be $$$0$$$ subsequences 01 and $$$0$$$ subsequences 10. Total number of angry comments will be equal to $$$0 \cdot 13 + 0 \cdot 37 = 0$$$.

In the third example one of the optimum ways to replace is 1100. Then there will be $$$0$$$ subsequences 01 and $$$4$$$ subsequences 10. Total number of angry comments will be equal to $$$0 \cdot 239 + 4 \cdot 7 = 28$$$.

In the fourth example one of the optimum ways to replace is 01101001. Then there will be $$$8$$$ subsequences 01 and $$$8$$$ subsequences 10. Total number of angry comments will be equal to $$$8 \cdot 5 + 8 \cdot 7 = 96$$$.

Example input:
0?1
2 3

Example output:
4

Example input:
?????
13 37

Example output:
0

Editorial:
Consider two adjacent question marks at positions $$$l$$$ and $$$r$$$ ($$$l < r$$$). Let $$$c_0$$$ zeros and $$$c_1$$$ ones be on the interval $$$(l, r)$$$. In case $$$s_l = 0$$$, $$$s_r = 1$$$ there will be written $$$(c_1 + 1) \cdot x + c_0 \cdot x + out = (c_0 + c_1 + 1) \cdot x + out = (r - l) \cdot x + out$$$ comments, where $$$out$$$ is the number of comments for subsequences, at least one element of which is outside $$$[l, r]$$$. In the case $$$s_l = 1$$$, $$$s_r = 0$$$ we get $$$(c_0 + 1) \cdot y + c_1 \cdot y + out = (c_0 + c_1 + 1) \cdot y + out = (r - l) \cdot y + out$$$ comments. Subtract the second from the first, we get $$$(r - l) \cdot (x - y)$$$. This means the following: if $$$x \geq y$$$, it is always better to change $$$01$$$ to $$$10$$$. That is, there is such an optimal substitution of $$$?$$$ by $$$0$$$ and $$$1$$$ that some prefix of $$$?$$$ are replaced by $$$1$$$, and the remaining by $$$0$$$. In the case of $$$x < y$$$, similarly, there will be some prefix of $$$0$$$, then suffix of $$$1$$$. For $$$\mathcal{O}(n)$$$ implementation you can count how many ones and zeros on each prefix and iterate over the separation boundary.