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
#include<bits/stdc++.h>

using namespace std;

int trucks(int p, int q, vector<int> &H, int k){
    if(p >= q) return 0;
    //cerr << p << " " << q << " ";
    pair<int, int> m = {0, 0};
    for(int i=p; i<q; i++)
        if(H[i] > m.first) m = {H[i], i};
    int c = m.second;
    //cerr << c << " ";

    int r = 0;
    if(c > p && H[c-1] + k < H[c]){
        r += H[c] - H[c-1] - k;
        H[c-1] += H[c] - H[c-1] - k;
    }
    if(c < q-1 && H[c+1] + k < H[c]){
        r += H[c] - H[c+1] - k;
        H[c+1] += H[c] - H[c+1] - k;
    }
    //cerr << r << "\n";
    return r + trucks(p, c, H, k) + trucks(c+1, q, H, k);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;
    vector<int> H(n);
    for(auto &it:H) cin >> it;
    cout << trucks(0, n, H, k) << "\n";
}