codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1659C.md (2761B)


      1 Source: https://codeforces.com/problemset/problem/1659/C
      2 
      3 C. Line Empire
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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.
     22 
     23 Consider a number axis. The capital of your empire is initially at $0$. There are $n$ unconquered kingdoms at positions $0 \lt x_1 \lt x_2 \lt \ldots \lt x_n$. You want to conquer all other kingdoms.
     24 
     25 There are two actions available to you:
     26 
     27 * 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|$.
     28 * 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.
     29 
     30 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.
     31 
     32 Find the minimum total cost to conquer all kingdoms. Your capital can be anywhere at the end.
     33 
     34 Input
     35 
     36 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.
     37 
     38 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$).
     39 
     40 The second line of each test case contains $n$ integers $x_1, x_2, \ldots, x_n$ ($1 \leq x_1 \lt x_2 \lt \ldots \lt x_n \leq 10^8$).
     41 
     42 The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     43 
     44 Output
     45 
     46 For each test case, output a single integer  — the minimum cost to conquer all kingdoms.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 4
     54 
     55 5 2 7
     56 
     57 3 5 12 13 21
     58 
     59 5 6 3
     60 
     61 1 5 6 21 30
     62 
     63 2 9 3
     64 
     65 10 15
     66 
     67 11 27182 31415
     68 
     69 16 18 33 98 874 989 4848 20458 34365 38117 72030
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 173
     76 171
     77 75
     78 3298918744
     79 ```
     80 
     81 Note
     82 
     83 Here is an optimal sequence of moves for the second test case:
     84 
     85 1. Conquer the kingdom at position $1$ with cost $3\cdot(1-0)=3$.
     86 2. Move the capital to the kingdom at position $1$ with cost $6\cdot(1-0)=6$.
     87 3. Conquer the kingdom at position $5$ with cost $3\cdot(5-1)=12$.
     88 4. Move the capital to the kingdom at position $5$ with cost $6\cdot(5-1)=24$.
     89 5. Conquer the kingdom at position $6$ with cost $3\cdot(6-5)=3$.
     90 6. Conquer the kingdom at position $21$ with cost $3\cdot(21-5)=48$.
     91 7. Conquer the kingdom at position $30$ with cost $3\cdot(30-5)=75$.
     92 
     93 The total cost is $3+6+12+24+3+48+75=171$. You cannot get a lower cost than this.