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
#include <iostream>
#include <queue>

constexpr int MAXN = 1e6+7;

int64_t a[MAXN];
bool handled[MAXN];

int main() {
    int64_t n,k;
    std::priority_queue<std::pair<int64_t, size_t>> pq;
    std::cin >> n >> k;
    for (size_t i = 0; i < n; i++) {
        std::cin >> a[i];
        pq.emplace(a[i], i);
    }
    int64_t total_cost = 0;
    while (!pq.empty()) {
        const auto [_, position] = pq.top();
        pq.pop();
        if (handled[position]) continue;
        handled[position] = true;
        if (position != 0) {
            size_t pp = position - 1;
            int64_t new_height = std::max(a[pp], a[position] - k);
            total_cost += new_height - a[pp];
            a[pp] = new_height;
            pq.emplace(a[pp], pp);
        }
        if (position != n-1) {
            size_t pp = position + 1;
            int64_t new_height = std::max(a[pp], a[position] - k);
            total_cost += new_height - a[pp];
            a[pp] = new_height;
            pq.emplace(a[pp], pp);
        }
    }
    std::cout << total_cost << '\n';
}