1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <vector>
using std::vector;

const int M = 501'013;
const int Q = 1'000'000'007;

int n, k, a[M], b[M], c[M];

int main() {
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    b[i] = -1;
    c[i] = a[i];
  }
  for (int ii = 0; ii < n; ii++) {
    int j = -1;
    for (int i = 0; i < n ; i++) if(b[i] == -1) {
      if (j == -1 || c[i] > c[j]) j = i;
    }
    b[j] = 0;
    if (j > 0 && c[j-1] < c[j]-k) c[j-1] = c[j]-k;
    if (j < n-1 && c[j+1] < c[j]-k) c[j+1] = c[j]-k;
  }
  long long ret = 0;
  for (int i = 0; i < n; i++) ret += c[i]-a[i];
  printf("%lld\n",ret);
  return 0;
}