Line Empire
Contest: Codeforces Round 782 (Div. 2)
Difficulty rating: 1500
Tags: binary search, brute force, dp, greedy, implementation, math

You are an ambitious king who wants to be the Emperor of The Reals. But to do that, you must first become Emperor of The Integers.

Consider a number axis. The capital of your empire is initially at $$$0$$$. There are $$$n$$$ unconquered kingdoms at positions $$$0<x_1<x_2<\ldots<x_n$$$. You want to conquer all other kingdoms.

There are two actions available to you:

- You can change the location of your capital (let its current position be $$$c_1$$$) to any other conquered kingdom (let its position be $$$c_2$$$) at a cost of $$$a\cdot |c_1-c_2|$$$.
- From the current capital (let its current position be $$$c_1$$$) you can conquer an unconquered kingdom (let its position be $$$c_2$$$) at a cost of $$$b\cdot |c_1-c_2|$$$. You cannot conquer a kingdom if there is an unconquered kingdom between the target and your capital.

Note that you cannot place the capital at a point without a kingdom. In other words, at any point, your capital can only be at $$$0$$$ or one of $$$x_1,x_2,\ldots,x_n$$$. Also note that conquering a kingdom does not change the position of your capital.

Find the minimum total cost to conquer all kingdoms. Your capital can be anywhere at the end.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$)  — the number of test cases. The description of each test case follows.

The first line of each test case contains $$$3$$$ integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq a,b \leq 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_1 < x_2 < \ldots < x_n \leq 10^8$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer  — the minimum cost to conquer all kingdoms.

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

Note:
Here is an optimal sequence of moves for the second test case:

1. Conquer the kingdom at position $$$1$$$ with cost $$$3\cdot(1-0)=3$$$.
2. Move the capital to the kingdom at position $$$1$$$ with cost $$$6\cdot(1-0)=6$$$.
3. Conquer the kingdom at position $$$5$$$ with cost $$$3\cdot(5-1)=12$$$.
4. Move the capital to the kingdom at position $$$5$$$ with cost $$$6\cdot(5-1)=24$$$.
5. Conquer the kingdom at position $$$6$$$ with cost $$$3\cdot(6-5)=3$$$.
6. Conquer the kingdom at position $$$21$$$ with cost $$$3\cdot(21-5)=48$$$.
7. Conquer the kingdom at position $$$30$$$ with cost $$$3\cdot(30-5)=75$$$.

The total cost is $$$3+6+12+24+3+48+75=171$$$. You cannot get a lower cost than this.

Example input:
4
5 2 7
3 5 12 13 21
5 6 3
1 5 6 21 30
2 9 3
10 15
11 27182 31415
16 18 33 98 874 989 4848 20458 34365 38117 72030

Example output:
173
171
75
3298918744

Editorial:
Clearly, we should always move from left to right. Also, assume $$$x_0=0$$$ for simplicity.
Let us analyze what our cost would look like. It will be composed of a part due to moving capitals, and a part due to conquering kingdoms. If we shift our capital from $$$x_i$$$ to $$$x_j$$$, the cost is $$$a\cdot(x_j-x_i)$$$. If we conquer kingdoms from $$$(i,j]$$$ with capital $$$x_i$$$, the cost is $$$b\cdot((x_{i+1}-x_i)+(x_{i+2}-x_i)+\ldots+(x_j-x_i))$$$, which can be written as $$$b\cdot(p_j-p_i-(j-i)\cdot x_i)$$$, where $$$p_i=x_0+x_1+\ldots+x_i$$$.
Now, notice that $$$x_j-x_i$$$ and $$$p_j-p_i$$$ are linear. Also, if we isolate the parts involving $$$x_j-x_i$$$, the sum will be like $$$(x_{j_1}-x_0)+(x_{j_2}-x_{j_1})+\ldots+(x_{j_f}-x_{j_{f-1}})=x_{j_f}-x_0$$$. This means we can simply write the final sum of this part as $$$a\cdot x_f$$$, where $$$x_f$$$ is the final position of the capital. We can say the same thing about $$$p_j-p_i$$$, except that the final kingdom conquered is always $$$x_n$$$. So the final sum of this part is always $$$b\cdot p_n$$$ ($$$x_0=p_0=0$$$, so they weren't written explicitly).
Our final cost, then, looks like $$$T=a\cdot x_f+b\cdot (p_n-C)$$$, where $$$C$$$ is composed of terms like $$$(j-i)\cdot x_i$$$. If we want to minimise $$$T$$$, we want to maximise $$$C$$$. That is achieved if we always increase $$$x_i$$$! Then we can write $$$$$$C=x_0+x_1+\ldots+x_{f-1}+\underbrace{x_f+\ldots+x_f}_{n-f\text{ }\mathrm{times}}=p_f+(n-f-1)\cdot x_f$$$$$$ We cannot increase beyond $$$x_f$$$ since that is the final position of our capital.
Hence, our final answer is given by $$$$$$\min_{f \in [0,n]}{(a\cdot x_f+b\cdot (p_n-p_f-(n-f-1)\cdot x_f))}$$$$$$
Time complexity: $$$\mathcal{O}(n)$$$