Rotation Sort

AtCoder

IDagc032_d

Time2000ms

Memory256MB

Difficulty—

You are given a permutation $p = (p_1, \ldots, p_N)$ of ${ 1, \ldots, N }$. You can perform the following two kinds of operations repeatedly in any order: * Pay a cost $A$. Choose integers $l$ and $r$ ($1 \leq l < r \leq N$), and shift $(p_l, \ldots, p_r)$ to the left by one. That is, replace $p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r$ with $p_{l + 1}, p_{l + 2}, \ldots, p_r, p_l$, respectively. * Pay a cost $B$. Choose integers $l$ and $r$ ($1 \leq l < r \leq N$), and shift $(p_l, \ldots, p_r)$ to the right by one. That is, replace $p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r$ with $p_r, p_l, \ldots, p_{r - 2}, p_{r - 1}$, respectively. Find the minimum total cost required to sort $p$ in ascending order. ## Constraints * All values in input are integers. * $1 \leq N \leq 5000$ * $1 \leq A, B \leq 10^9$ * $(p_1 \ldots, p_N)$ is a permutation of ${ 1, \ldots, N }$. ## Input Input is given from Standard Input in the following format: $N$ $A$ $B$ $p_1$ $\cdots$ $p_N$ [samples]

Samples

Input #1

3 20 30
3 1 2

Output #1

20

Shifting $(p_1, p_2, p_3)$ to the left by one results in $p = (1, 2, 3)$.

Input #2

4 20 30
4 2 3 1

Output #2

50

One possible sequence of operations is as follows:

*   Shift $(p_1, p_2, p_3, p_4)$ to the left by one. Now we have $p = (2, 3, 1, 4)$.
*   Shift $(p_1, p_2, p_3)$ to the right by one. Now we have $p = (1, 2, 3, 4)$.

Here, the total cost is $20 + 30 = 50$.

Input #3

1 10 10
1

Output #3

Input #4

4 1000000000 1000000000
4 3 2 1

Output #4

3000000000

Input #5

9 40 50
5 3 4 7 6 1 2 9 8

Output #5

API Response (JSON)

{
  "problem": {
    "name": "Rotation Sort",
    "description": {
      "content": "You are given a permutation $p = (p_1, \\ldots, p_N)$ of ${ 1, \\ldots, N }$. You can perform the following two kinds of operations repeatedly in any order: *   Pay a cost $A$. Choose integers $l$ and ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc032_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a permutation $p = (p_1, \\ldots, p_N)$ of ${ 1, \\ldots, N }$. You can perform the following two kinds of operations repeatedly in any order:\n\n*   Pay a cost $A$. Choose integers $l$ and ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments