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
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define int long long

using namespace std;

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n,k;
    cin>>n>>k;
    set<pair<int,int>>st;
    int a[n];
    for(int i = 0;i<n;i++){
        cin>>a[i];
        st.insert(make_pair(a[i],i));
    }
    int ans = 0;
    while(st.size()){
        int h = (*--st.end()).first,ps = (*--st.end()).second;
        //cout<<h<<' '<<ps<<endl;
        st.erase(--st.end());
        if(a[ps] > h){
            continue;
        }
        ans += h-a[ps];
        a[ps] = h;
        if(ps > 0 && a[ps-1] < h-k){
            st.insert(make_pair(h-k,ps-1));
        }
        if(ps < n-1 && a[ps+1] < h-k){
            st.insert(make_pair(h-k,ps+1));
        }
    }
    cout<<ans;
}