TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

68.8% (22/32)

Submission's AC Ratio

25.5% (36/141)

Tags

Description

見習魔法師宜恩最近在和他的師父芒果學習水果魔法,他們現在在山上修練。
具體來說,有 $N$ 座山排成一列,由左數來的第 $i$ 座山的高度為 $a_i$,宜恩一開始在第 $1$ 座山上,總共有 $K$ 點魔力值,他的目標是抵達第 $N$ 座山越快越好,這樣他就可以去刷題了。
宜恩在第 $i$($1\le i<n$) 座山時他可以做兩種事:

  • 花費 $| a_i-a_{i+1}|$ 的時間前進到第 $i+1$ 座山。
  • 花費 $1$ 點的魔力值施展水果魔法(水果魔法很厲害所以不需要花費時間),讓第 $i+1$ 座山的高度增加 $1$。需要注意的是芒果在第 $N$ 座山上,他不會被魔法影響所以宜恩沒有辦法讓第 $N$ 座山變高。

宜恩很好奇他需要多少時間才能抵達第 $N$ 座山,請你幫幫他!

Input Format

第一行會有兩個整數 $N$, $K$,代表一共有幾座山跟宜恩的魔力值。
第二行會有一個陣列 $a_1\sim a_N$,代表每座山的高度。

對於所有測試資料:

  • $1 \leq N \leq 10 ^ 6 $
  • $0 \leq K \leq 10 ^ {18} $
  • $0 \leq a_i \leq 10 ^ {12} $

Output Format

輸出一個整數,表示宜恩最少需要花多少時間才能抵達第 $N$ 座山。

Sample Input 1

5 3
4 2 5 1 3

Sample Output 1

5

Sample Input 2

5 8
6 2 1 3 7

Sample Output 2

5

Hints

範例測資 1 解釋:其中一種最少時間的方法會使山最後變成$4$ $4$ $5$ $2$ $3$

範例測資 2 解釋:其中一種最少時間的方法會使山最後變成$6$ $5$ $4$ $4$ $7$

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~12 $N\leq 5000,K\le 2\times 10^ 7,a_i\leq 5000$($1\leq i\leq N$) 28
3 1~6, 12~21 $\exists i$($1\leq i\leq N$)使得 $a_j\geq a_{j+1}$($1\leq j< i$),$a_j\leq a_{j+1}$($i\leq j<N$) 25
4 0~41 無其他限制 47

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 65536 65536 1 2 4
1 2000 65536 65536 1 2 3 4
2 2000 65536 65536 2 3 4
3 2000 65536 65536 2 3 4
4 2000 65536 65536 2 3 4
5 2000 65536 65536 2 3 4
6 2000 65536 65536 2 3 4
7 2000 65536 65536 2 4
8 2000 65536 65536 2 4
9 2000 65536 65536 2 4
10 2000 65536 65536 2 4
11 2000 65536 65536 2 4
12 2000 65536 65536 2 3 4
13 2000 65536 65536 3 4
14 2000 65536 65536 3 4
15 2000 65536 65536 3 4
16 2000 65536 65536 3 4
17 2000 65536 65536 3 4
18 2000 65536 65536 3 4
19 2000 65536 65536 3 4
20 2000 65536 65536 3 4
21 2000 65536 65536 3 4
22 2000 65536 65536 4
23 2000 65536 65536 4
24 2000 65536 65536 4
25 2000 65536 65536 4
26 2000 65536 65536 4
27 2000 65536 65536 4
28 2000 65536 65536 4
29 2000 65536 65536 4
30 2000 65536 65536 4
31 2000 65536 65536 4
32 2000 65536 65536 4
33 2000 65536 65536 4
34 2000 65536 65536 4
35 2000 65536 65536 4
36 2000 65536 65536 4
37 2000 65536 65536 4
38 2000 65536 65536 4
39 2000 65536 65536 4
40 2000 65536 65536 4
41 2000 65536 65536 4