Line Empire Codeforces

We are given $N$ cities on an integer number line at positions $0<x_1<x_2<...<x_N$, where our capital is initially at position 0. Initially only the capital is conquered. We can make the following moves:

1. Move the capital at $x_i$ to any conquered city at $x_j$ for a price of $a\cdot |x_i-x_j|$,
2. Conquer an unconquered city at position $x_j$ where our capital is at $x_i$ for a price of $b\cdot |x_i-x_j|$ so long as all cities on path between capital and unconquered city are conquered already.

We are looking for the minimum price to conquer all cities. First let's make some observations:

• We are forced to conquer the cities in the order $x_1, x_2, ..., x_N$ because of the condition that all cities on the path from the capital to the unconquered city must be already conquered.
• The first move must be to conquer $x_1$.
• We never want to move the capital left.

Let's play with a scenario.

0 -- X1 -- X2 -- X3 -- X4

Suppose the sequence of moves which minimises the price payed ends with the capital at $X3$. Then, we must pay price $a\cdot X3$ for capital movement. Since the price function is linear, the moments  when we move the capital do not affect the cost payed for capital movement, i.e. if we move the capital from $0$ to $X1$, then to $X3$, this costs the same as moving the capital straight to $X3$ from $0$.

However, since having the capital closer to the right reduces the cost payed for conquering, we always want to move the capital right as soon as we can. Pictorially this is because if we do the conquering first we pay prices as follows

0 -- X1 -- X2 -- X3 -- X4

-------->

-------------->

--------------------->

----------------------------->

********************

Here --> is the conquering cost between the neighboring cities and *** is the capital moving cost. However, if we move the capital as soon as we can, then we have

0 -- X1 -- X2 -- X3 -- X4

------->

******

            ----->

            ******

                     ------>

                     *******

                                ------>

So, as already established the capital moving cost is the same, however, the conquering cost is much less, since we do not repeat the costs as in the first picture. In general, if the capital ends up at $X_i$, the total price payed is therefore 

$$X_i\cdot (a+b) + b\cdot\sum_{j=i+1}^{N}{X_j-X_i}=X_i\cdot (a+b)+b\cdot(S_{N}-S_{i}-(n-i)\cdot X_i)$$

We can precompute prefix sums $S_{i}$ on $X$ in $O(N)$ so that this value is computable in $O(1)$ for any $i$.

We are missing a detail: how do we know where the capital ends up at the end of a sequence of moves which minimises the price? Well we can just try every possible $0\leq i\leq N$ and keep whichever achieves the minimum price.