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
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <deque>
#include <map>
#include <queue>
#include <climits>
using namespace std;
using ll=long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, K;
    cin >> N >> K;
    vector<int> V(N);
    priority_queue<pair<int, int>, vector<pair<int, int>>> pq;
    for(int i=0; i<N; i++){
        cin>>V[i];
        pq.push({V[i], i});
    }
    ll wynik=0;
    vector<bool> seen(N, false);
    while(!pq.empty()){
        auto a = pq.top();
        int b = a.second;
        pq.pop();
        if(!seen[b]){
            int c=b-1;
            while(V[c]<=V[c+1] && c>=0){
                if(V[c]+K<V[c+1]){
                    wynik+=V[c+1]-V[c]-K;
                    V[c]=V[c+1]-K;
                }
                c--;
            }
            int d=b+1;
            while(V[d]<=V[d-1] && d<N){
                if(V[d]+K<V[d-1]){
                    wynik+=V[d-1]-V[d]-K;
                    V[d]=V[d-1]-K;
                }
                d++;
            }
        }
    }
    cout << wynik << '\n';

    return 0;
}