C - 階段状の花壇 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 333 点

問題文

高橋君は庭師として働いており、一列に並んだ花壇の手入れを任されています。

花壇は N 個あり、それぞれの花壇には 1 から N までの番号が付けられています。各花壇 i（ 1 \leq i \leq N ）には、現在 A_i 本の花が植えられています。

高橋君の上司によると、花壇の列が美しい状態であるための条件は「すべての隣り合う花壇について、花の本数の差の絶対値が K 以下であること」だそうです。すなわち、手入れ後の各花壇 i の花の本数を B_i としたとき、すべての i（ 1 \leq i \leq N - 1 ）について |B_i - B_{i+1}| \leq K が成り立つとき、花壇の列は美しいとみなされます。

高橋君は新しく花を植えることはできますが、すでに植えられている花を抜くことはできません。具体的には、各花壇 i に対して 0 本以上の花を追加し、花の本数を A_i 本から B_i 本に増やすことができます。ここで、各 B_i は B_i \geq A_i を満たす整数でなければなりません。

高橋君は、花壇の列を美しい状態にするために追加する花の合計本数 \displaystyle\sum_{i=1}^{N} (B_i - A_i) を最小化したいと考えています。この最小値を求めてください。

なお、すべての B_i を十分大きな同じ値にすれば条件を満たせるため、花の追加のみで美しい状態にすることは常に可能です。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

N K
A_1 A_2 \ldots A_N
  • 1 行目には、花壇の数を表す整数 N と、隣り合う花壇間で許容される花の本数の差を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各花壇 i に現在植えられている花の本数を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

花壇の列を美しい状態にするために追加が必要な花の合計本数の最小値を 1 行で出力せよ。

入力例 1

3 2
1 5 3

出力例 1

2

入力例 2

5 3
2 4 5 3 1

出力例 2

0

入力例 3

7 10
5 30 15 50 20 100 85

出力例 3

235

Score : 333 pts

Problem Statement

Takahashi works as a gardener and is in charge of maintaining a row of flower beds.

There are N flower beds, each numbered from 1 to N. Each flower bed i (1 \leq i \leq N) currently has A_i flowers planted in it.

According to Takahashi's boss, the condition for the row of flower beds to be in a beautiful state is that "for all adjacent flower beds, the absolute difference in the number of flowers is at most K." In other words, if we denote the number of flowers in each flower bed i after maintenance as B_i, then the row of flower beds is considered beautiful when |B_i - B_{i+1}| \leq K holds for all i (1 \leq i \leq N - 1).

Takahashi can plant new flowers but cannot remove flowers that are already planted. Specifically, for each flower bed i, he can add 0 or more flowers to increase the number of flowers from A_i to B_i. Here, each B_i must be an integer satisfying B_i \geq A_i.

Takahashi wants to minimize the total number of flowers added \displaystyle\sum_{i=1}^{N} (B_i - A_i) in order to make the row of flower beds beautiful. Find this minimum value.

Note that it is always possible to achieve a beautiful state by only adding flowers, since the condition can be satisfied by setting all B_i to the same sufficiently large value.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9
  • All inputs are integers

Input

N K
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of flower beds and an integer K representing the allowed difference in the number of flowers between adjacent flower beds, separated by a space.
  • The second line contains integers A_1, A_2, \ldots, A_N representing the number of flowers currently planted in each flower bed i, separated by spaces.

Output

Output in one line the minimum total number of flowers that need to be added to make the row of flower beds beautiful.

Sample Input 1

3 2
1 5 3

Sample Output 1

2

Sample Input 2

5 3
2 4 5 3 1

Sample Output 2

0

Sample Input 3

7 10
5 30 15 50 20 100 85

Sample Output 3

235