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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>

using namespace std;

int n, k;
int A[1'003];
bool vis[1'003];

class Event {
public:
    int pos, val;
    Event(int p, int v) {
        pos = p;
        val = v;
    }

    bool operator<(const Event& other) const {
        return val < other.val;
    }

    void print() const {
        cout << "Event (pos: " << pos << ", val: " << val << ")" << '\n';
    }
};

priority_queue<Event> events;

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> A[i];
        events.push(Event(i, A[i]));
    }

    int output = 0;
    while (!events.empty()) {
        Event e = events.top();
        events.pop();
        if (vis[e.pos] || e.pos < 1 || e.pos > n) {
            continue;
        }

        // cout << "Processing event: ";
        // e.print();
        
        vis[e.pos] = true;
        
        if (true == vis[e.pos - 1]) {
            int diff = A[e.pos - 1] - A[e.pos];
            if (diff > k) {
                output += diff - k;
                A[e.pos] += diff - k;
            }
        }

        if (true == vis[e.pos + 1]) {
            int diff = A[e.pos + 1] - A[e.pos];
            if (diff > k) {
                output += diff - k;
                A[e.pos] += diff - k;
            }
        }

        events.push(Event(e.pos + 1, A[e.pos]));
        events.push(Event(e.pos - 1, A[e.pos]));
    }

    // for (int i = 1; i <= n; ++i) {
    //     cout << A[i] << ' ';
    // }
    // cout << '\n';

    cout << output << '\n';
    return 0;
}