Restorer Distance
Contest: Codeforces Round 643 (Div. 2)
Difficulty rating: 2100
Tags: binary search, greedy, math, sortings, ternary search

You have to restore the wall. The wall consists of $$$N$$$ pillars of bricks, the height of the $$$i$$$-th pillar is initially equal to $$$h_{i}$$$, the height is measured in number of bricks. After the restoration all the $$$N$$$ pillars should have equal heights.

You are allowed the following operations:

- put a brick on top of one pillar, the cost of this operation is $$$A$$$;
- remove a brick from the top of one non-empty pillar, the cost of this operation is $$$R$$$;
- move a brick from the top of one non-empty pillar to the top of another pillar, the cost of this operation is $$$M$$$.

You cannot create additional pillars or ignore some of pre-existing pillars even if their height becomes $$$0$$$.

What is the minimal total cost of restoration, in other words, what is the minimal total cost to make all the pillars of equal height?

Input format:
The first line of input contains four integers $$$N$$$, $$$A$$$, $$$R$$$, $$$M$$$ ($$$1 \le N \le 10^{5}$$$, $$$0 \le A, R, M \le 10^{4}$$$) — the number of pillars and the costs of operations.

The second line contains $$$N$$$ integers $$$h_{i}$$$ ($$$0 \le h_{i} \le 10^{9}$$$) — initial heights of pillars.

Output format:
Print one integer — the minimal cost of restoration.

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

Example input:
3 1 100 100
1 3 8

Example output:
12

Example input:
3 100 1 100
1 3 8

Example output:
9

Editorial:
First of all let's do $$$M = \min(M, A + R)$$$ — this is true since we can emulate moving by adding+removing. After that it is never profitable to add and remove in one solution, since we can always move instead.
Suppose we have fixed $$$H$$$ — the resulting height for all pillars. How can we calculate the minimal cost for given $$$H$$$? Some pillars have no more than $$$H$$$ bricks, let the total number of missing bricks in these pillars be $$$P$$$. Other pillars have no less than $$$H$$$ bricks, let the total number of extra bricks in these pillars be $$$Q$$$. If $$$P \ge Q$$$ then we are missing $$$(P - Q)$$$ bricks in total, so we have to make $$$(P - Q)$$$ additions. There won't be any more additions or removals, and we have to do at least $$$Q$$$ moves since we have to somehow get rid of extra bricks from those pillars which have more than $$$H$$$ bricks initially. It is clear that $$$Q$$$ moves is enough. Therefore the total cost will be $$$C = A(P - Q) + MQ$$$. Similarly, if $$$Q \ge P$$$ then the total cost will be $$$C = R(Q - P) + MP$$$.
Let's now assume that $$$P \ge Q$$$, we have exactly $$$X$$$ pillars with no more than $$$H$$$ bricks and exactly $$$N - X$$$ pillars with strictly more than $$$H$$$ bricks. Let's try to increase $$$H$$$ by 1 and see how the total cost will change. $$$P' = P + X$$$, $$$Q' = Q - (N - X) = Q - N + X$$$. $$$C' = A(P' - Q') + MQ' = A(P + X - Q + N - X) + M(Q - N + X) = A(P - Q) + MQ + AN - M(N - X)$$$. We can see that the total cost has changed by $$$AN - M(N - X)$$$. While $$$X$$$ is constant the cost change will be constant. What are the moments when $$$X$$$ changes? When $$$H$$$ is equal to the initial height of some pillar. Therefore the cost as a function of $$$H$$$ is piecewise linear with breakpoints in points corresponding to initial heights.
There is a nuance — we have assumed $$$P \ge Q$$$. The same thing will be true for $$$P \le Q$$$ but there can be additional breakpoints when we change between these two states. This change will happen only once for $$$H \approx \frac{\sum h_{i}}{N}$$$ (approximate equality here means that this point can be non-integral so we should add both $$$\lfloor \frac{\sum h_{i}}{N} \rfloor$$$ and $$$\lceil \frac{\sum h_{i}}{N} \rceil$$$ as breakpoints).
The minima of piecewise linear function are in breakpoints so it is enough to calculate the cost for breakpoints (initial heights and $$$H \approx \frac{\sum h_{i}}{N}$$$) and choose minimal of them.
To calculate the cost for given $$$H$$$ fast we can sort the initial heights and calculate prefix sums of heights. Then using binary search we can determine which pillars have height less than $$$H$$$ and greater than $$$H$$$ and then calculate $$$P$$$ and $$$Q$$$ using prefix sums. We can use two pointers instead of binary searches but it will not improve the total complexity which is $$$O(N \log N)$$$ due to sorting (and binary searches if we are using them).