[Solution] Line Empire solution codeforces

Line Empire solution codeforces – 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.

[Solution] Line Empire solution codeforces

Consider a number axis. The capital of your empire is initially at 00. There are 𝑛n unconquered kingdoms at positions 0<𝑥1<𝑥2<<𝑥𝑛0<x1<x2<…<xn. 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 𝑐1c1) to any other conquered kingdom (let its position be 𝑐2c2) at a cost of 𝑎|𝑐1𝑐2|a⋅|c1−c2|.
  • From the current capital (let its current position be 𝑐1c1) you can conquer an unconquered kingdom (let its position be 𝑐2c2) at a cost of 𝑏|𝑐1𝑐2|b⋅|c1−c2|. 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 00 or one of 𝑥1,𝑥2,,𝑥𝑛x1,x2,…,xn. 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.

[Solution] Line Empire solution codeforces

The first line contains a single integer 𝑡t (1𝑡10001≤t≤1000)  — the number of test cases. The description of each test case follows.

The first line of each test case contains 33 integers 𝑛n𝑎a, and 𝑏b (1𝑛21051≤n≤2⋅1051𝑎,𝑏1051≤a,b≤105).

The second line of each test case contains 𝑛n integers 𝑥1,𝑥2,,𝑥𝑛x1,x2,…,xn (1𝑥1<𝑥2<<𝑥𝑛1081≤x1<x2<…<xn≤108).

The sum of 𝑛n over all test cases does not exceed 21052⋅105.

Output

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

[Solution] Line Empire solution codeforces

Example
input

Copy
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
output

Copy
173
171
75
3298918744

Line Empire solution codeforces

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

  1. Conquer the kingdom at position 11 with cost 3(10)=33⋅(1−0)=3.
  2. Move the capital to the kingdom at position 11 with cost 6(10)=66⋅(1−0)=6.
  3. Conquer the kingdom at position 55 with cost 3(51)=123⋅(5−1)=12.
  4. Move the capital to the kingdom at position 55 with cost 6(51)=246⋅(5−1)=24.
  5. Conquer the kingdom at position 66 with cost 3(65)=33⋅(6−5)=3.
  6. Conquer the kingdom at position 2121 with cost 3(215)=483⋅(21−5)=48.
  7. Conquer the kingdom at position 3030 with cost 3(305)=753⋅(30−5)=75.

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

 

For Solution

Click here

Leave a Comment