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
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  size_t n, k, r = 0;
  cin >> n >> k;
  vector< size_t > h(n);
  typedef map< size_t, set< size_t > > m_t;
  m_t m;
  for (n = 0; n < h.size(); ++n) {
    cin >> h[n];
    m[h[n]].insert(n);
  }
  while (m.size()) {
    m_t::iterator it = m.end();
    n = *((--it)->second.begin());
    it->second.erase(it->second.begin());
    if (!it->second.size())
      m.erase(it);
    for (size_t d = 0; d < 2; ++d) {
      size_t z = n + d * 2 - 1;
      if (z < h.size())
        if (h[z] + k < h[n]) {
          m[h[z]].erase(z);
          if (!m[h[z]].size())
            m.erase(h[z]);
          r += h[n] - (h[z] + k);
          m[h[z] = h[n] - k].insert(z);
        }
    }
  }
  cout << r << '\n';
}