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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <algorithm>
#include <cstdio>
#include <vector>

struct Item {
  int height;
  int index;

  bool operator<(const Item& item) const { return height < item.height; }
};

int fixItem(std::vector<int>& heights, const int index, const int k) {
  const int left = index - 1;
  const int right = index + 1;
  int sum = 0;
  if (0 <= left) {
    const int diff = heights[left] - heights[index] - k;
    if (0 < diff) {
      heights[index] += diff;
      sum += diff;
    }
  }
  if (right < heights.size()) {
    const int diff = heights[right] - heights[index] - k;
    if (0 < diff) {
      heights[index] += diff;
      sum += diff;
    }
  }
  return sum;
}

int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  std::vector<int> heights;
  std::vector<Item> items;
  heights.resize(n);
  items.resize(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &heights[i]);
  }

  int sum = 0;
  while (true) {
    int subSum = 0;
    for (int i = 0; i < n; ++i) {
      items[i].index = i;
      items[i].height = heights[i];
    }
    std::sort(items.rbegin(), items.rend());
    for (const auto& item : items) {
      subSum += fixItem(heights, item.index, k);
    }
    if (subSum == 0) {
      break;
    } else {
      sum += subSum;
    }
  }
  printf("%d\n", sum);
}