[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.


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

[Solution] Line Empire solution codeforces


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


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