N Machines
Contest: Codeforces Round 829 (Div. 1)
Difficulty rating: 3300
Tags: binary search, brute force, greedy

You have been invited as a production process optimization specialist to some very large company. The company has $$$n$$$ machines at its factory, standing one behind another in the production chain. Each machine can be described in one of the following two ways: $$$(+,~a_i)$$$ or $$$(*,~a_i)$$$.

If a workpiece with the value $$$x$$$ is supplied to the machine of kind $$$(+,~a_i)$$$, then the output workpiece has value $$$x + a_i$$$.

If a workpiece with the value $$$x$$$ is supplied to the machine of kind $$$(*,~a_i)$$$, then the output workpiece has value $$$x \cdot a_i$$$.

The whole production process is as follows. The workpiece with the value $$$1$$$ is supplied to the first machine, then the workpiece obtained after the operation of the first machine is supplied to the second machine, then the workpiece obtained after the operation of the second machine is supplied to the third machine, and so on. The company is not doing very well, so now the value of the resulting product does not exceed $$$2 \cdot 10^9$$$.

The directors of the company are not satisfied with the efficiency of the production process and have given you a budget of $$$b$$$ coins to optimize it.

To optimize production you can change the order of machines in the chain. Namely, by spending $$$p$$$ coins, you can take any machine of kind $$$(+,~a_i)$$$ and move it to any place in the chain without changing the order of other machines. Also, by spending $$$m$$$ coins, you can take any machine of kind $$$(*,~a_i)$$$ and move it to any place in the chain.

What is the maximum value of the resulting product that can be achieved if the total cost of movements that are made should not exceed $$$b$$$ coins?

Input format:
The first line contains four integers $$$n$$$, $$$b$$$, $$$p$$$ and $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le b, p, m \le 10^9$$$) — the number of machine at the factory, your budget and costs of movements of both kinds of machines.

Each of the following $$$n$$$ lines contains description of a machine. The description begins with one of the following characters: "+" or "*", that denotes the kind of the machine. Then an integer $$$a_i$$$ follows ($$$1 \le a_i \le 2 \cdot 10^9$$$).

It's guaranteed that the current value of the resulting product does not exceed $$$2 \cdot 10^9$$$.

Output format:
Print one integer — the maximum value of the resulting product that can be achieved if the total cost of movements that are made does not exceed $$$b$$$ coins.

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

Note:
In the first example our budget is too low to move machine $$$(*,~2)$$$, but we can move both machines $$$(+,~1)$$$ to the beginning of the chain. So the final chain will be $$$(+,~1)$$$ $$$(+,~1)$$$ $$$(*,~2)$$$. If the workpiece with the value $$$1$$$ is supplied to the first machine, its value will be changed in the following way: $$$1, 2, 3, 6$$$.

In the second example we can move only one machine. Let's move machine $$$(+,~2)$$$ to the beginning of the chain. The final chain will be $$$(+,~2)$$$ $$$(*,~2)$$$ $$$(+,~1)$$$ $$$(*,~3)$$$. The value of the workpiece will be changed in the following way: $$$1, 3, 6, 7, 21$$$.

In the third example we can place machine $$$(*,~4)$$$ before the machine $$$(*,~5)$$$, and move machine $$$(+,~3)$$$ to the beginning of the chain. The final chain will be $$$(+,~3)$$$ $$$(*,~2)$$$ $$$(+,~1)$$$ $$$(+,~1)$$$ $$$(+,~1)$$$ $$$(+,~1)$$$ $$$(*,~4)$$$ $$$(*,~5)$$$. The value of the workpiece will be changed in the following way: $$$1, 4, 8, 9, 10, 11, 12, 48, 240$$$.

Example input:
3 2 1 3
* 2
+ 1
+ 1

Example output:
6

Example input:
4 2 2 2
* 2
+ 1
* 3
+ 2

Example output:
21

Editorial:
Let $$$C$$$ bi the maximum value of the resulting product before any movements. The problem statement says that it is guaranteed that $$$C \le 2 \cdot 10^9$$$.
• Observation 0 — after each movements the value of the resulting product is not greater than $$$\frac{C^2}{4}$$$.
• Observation 1 — each machine of kind $$$(*, a_i)$$$ should be moved to the end of the sequence, and each machine of kind $$$(+, a_i)$$$ — to the beginning of the sequence, and the order of movements does not make sense.
• Observation 2 — there are at most $$$\log_2{C}$$$ non-trivial machines of kind $$$(*, a_i)$$$ (such machines that $$$a_i \neq 1$$$). We will need some more strong observation for machines of kind $$$(*, a_i)$$$, but this will be useful too.
• Observation 3 — if there are two machines $$$(*, a_i)$$$, $$$(*, a_j)$$$, where $$$i < j$$$ and $$$a_i >= a_j$$$, then in optimal answer machine $$$j$$$ may be moved if and only if machine $$$i$$$ is moved too. It is true because we could increase the answer otherwise, by moving machine $$$i$$$ instead of machine $$$j$$$.
The last two observations says that there are not many subsets of machines of kind $$$(*, a_i)$$$ (that satisfies the property from observation 3). Let's say that there are $$$F(C)$$$ such subsets, in the end of the editorial we will estimate this value.
Let's pick out subsegments of machines of kind $$$(+, a_i)$$$ between machines of kind $$$(*, a_i)$$$, sort them and count prefix sums. There will be not more than $$$\log_2{C} + 1$$$ such segments. In the optimal answer some maximums will be moved from each of the segments.
Let's fix some subset of machines of kind $$$(*, a_i)$$$, that will be moved to the end, and count the current value of the output product. Consider some element $$$(+, a_j)$$$ in the array. Let the product of machines $$$(*, a_i)$$$ to the left of it be $$$lmul$$$, and to the right of it — to be $$$rmul$$$. Now if we move this element to the beginning of the array, the value of the resulting product will increase by $$$\frac{lmul-1}{lmul} \cdot rmul \cdot a_j$$$. Let's call this $$$profit_j$$$. Now we have to find the sum of some numbers of maximum values $$$profit_j$$$.
Let's use binary search to find some "critical" value $$$profit$$$: such value that all elements $$$profit_j \ge profit$$$ will be moved to the beginning. $$$profit_j$$$ of each element is not greater than $$$C^2/4$$$. Inside binary search we have to iterate over all segments of elements $$$(+, a_i)$$$ and find the number of elements with $$$profit_j \ge profit$$$ inside this segment using binary search. We have to check if we can to move the selected amount of elements to the beginning of the array to understand how to move borders of the external binary search.
After we find the critical value $$$profit$$$, let's iterate over all segments $$$(+, a_i)$$$ and add the sum of elements that are $$$profit_j \ge profit$$$ to the answer. Separately let's consider elements with $$$profit_j$$$ = $$$profit - 1$$$. We could move some of them to the beginning too. Let's update the answer with this value.
Time complexity: $$$O(F(C) \log^3_2(C) + n \cdot \log_2(n))$$$. It should be noted that this estimate is actually higher than in fact.
Let's estimate the value $$$F(C)$$$ now:
• Consider some sequence $$$b_1, b_2, \dots, b_k$$$, such that $$$b_1 \cdot b_2 \cdot$$$ $$$\dots$$$ $$$\cdot b_k \le C$$$ and $$$2 \le b_i$$$
• Sort it by ascending, $$$b_1 \le b_2 \le \dots \le b_k$$$ — the product of elements will not change and the number of "interesting" subsets will not become smaller.
• Replace all the smallest elements of the sequence with $$$2$$$, the second minimums with $$$3$$$ and so on. If there are smaller number of elements equals to $$$x$$$ than elements equals to $$$y$$$ and $$$x < y$$$, let's swap their numbers. Now the number of interesting subsets is not changed, $$$b_1 \cdot b_2 \cdot$$$ $$$\dots$$$ $$$\cdot b_k$$$ is not increased. The sequence looks like $$$2, 2, \dots, 3, \dots, 4, \dots$$$ now.
• The number of interesting subsets in the new sequence equals to $$$(cnt_2 + 1) \cdot (cnt_3 + 1) \cdot \dots$$$, where $$$cnt_x$$$ is the number of elements if sequence equals to $$$x$$$.
• (Let's run the code that will brute-force over all sequences of such kind and see that the number of interesting subsets is $$$4608$$$, which is achieved on sequence $$$2, 2, 2, 3, 3, 4, 4, 5, 6, 7, 8, 9, 10, 11$$$)
• Let's continue estimating this value "fairly": the elements of the sequence do not exceed $$$12$$$ because $$$13! > C$$$. Let's replace each number with a prime number corresponding to it by order: $$$p_2 = 2, p_3 = 3, p_4 = 5, p_5 = 7, p_6 = 11, ...$$$ and replace all elements $$$x$$$ with $$$p_x$$$. The product of elements will increate in at most $$$\max\limits_{x}{((\frac{p_x}{x})^{\log_x(C)})}$$$ times, so the product will not exceed $$$\max\limits_{x}{(C^{\log_x{(p_x)}})}$$$. It is easy to check that the maximum is achieved in $$$x=6$$$, so the product is not greater than $$$C^{\log_6{11}}$$$ $$$\le 3 \cdot 10^{12}$$$.
• The number of interesting subsets of our sequence does not exceed the number of divisors of received numbers that can be estimated as $$$(3 \cdot 10^{12})^{(1/3)}$$$ $$$\le 15000$$$