No.595 Mountain Climbing
ei1333333
はむこProblem Statement
$N$ points $1, 2, \dots, N$ are lined up in order on a straight line, and the elevation of point $i$ is $H_i$.
Ushi is currently at point $1$. Ushi wants to visit each of the $N - 1$ points other than point $1$ at least $1$ time. The ending point may be anywhere.
Ushi can perform the following $2$ types of operations any number of times.
- Move to an adjacent point. Since Ushi is not good at climbing, moving from the current point $i$ to an adjacent point $j$ consumes energy $\max(0, H_j - H_i)$.
- Warp to any point of Ushi's choice. Each $1$ warp consumes energy $P$.
Find the minimum energy required to visit all the points.
Input
$N$ $P$ $H_1\ H_2\ \dots\ H_N$
Line $1$ contains the number of points $N(2 \le N \le 200\ 000)$ and the energy consumption per $1$ warp $P(0 \le P \le 10^9)$, separated by a space.
Line $2$ contains $N$ integers separated by spaces. The $i$-th integer $H_i(0 \le H_i \le 10^9)$ represents the elevation of point $i$.
Output
Output, on $1$ line, the minimum energy for Ushi to visit all the points.
Sample
Sample 1
Input
6 3 1 1 10 10 100 100
Output
3
For example, warp from point $1$ to point $6$, consuming energy $3$. Then move through points $5, 4, 3, 2$ in this order.
Sample 2
Input
6 5 100 1 3 0 10 100
Output
7
For example, move through points $1, 2, 3$ in this order, then warp from point $3$ to point $6$. Then move through points $5, 4$ in this order.
Moving from point $2$ to $3$ consumes energy $2$, and warping from point $3$ to $6$ consumes energy $5$, for a total of $7$.
Sample 3
Input
10 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000
Output
5000000000
Note that the answer may not fit in a 32bit integer type.
Sample 4
Input
4 0 0 1000000000 0 1000000000
Output
0
It suffices to visit all the points by warping.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。