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

#define nd second
#define st first

int main() {

    int n,k;
    cin>>n>>k;
    priority_queue<pair<int,int> > q;
    vector<int> vals;
    for(int i=0; i<n; i++) {
        int x;
        cin>>x;
        q.push({x, i});
        vals.push_back(x);
    }

    long long sum = 0;
    while(!q.empty()) {
        auto t = q.top();
        q.pop();
        if(vals[t.nd] > t.st)
            continue;
    //    cout<<t.st<<" "<<t.nd<<endl;
        if(t.nd>0) {
            sum += max(0, t.st - vals[t.nd-1] - k);
            if(t.st - vals[t.nd-1] - k>0) {
                vals[t.nd-1] += max(0, t.st - vals[t.nd-1] - k);
                q.push({vals[t.nd-1], t.nd-1});
            }
            else
                vals[t.nd-1] += max(0, t.st - vals[t.nd-1] - k);
        }
        if(t.nd<n-1) {
            sum += max(0, t.st - vals[t.nd+1] - k);
            if(t.st - vals[t.nd+1] - k>0) {
                vals[t.nd+1] += max(0, t.st - vals[t.nd+1] - k);
                q.push({vals[t.nd+1], t.nd+1});
            }
            else 
                vals[t.nd+1] += max(0, t.st - vals[t.nd+1] - k);
        }
    }
  //  for(int i=0; i<n; i++)
 //       cout<<vals[i]<<" ";
 //   cout<<endl;

    cout<<sum;

}