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
#include <iostream>
#include <vector>
#include <set>
#include <functional>

struct Element {
    long long wartosc;
    int lewySasiad;
    int prawySasiad;
};

int main(int argc, char* argv[]) {
    bool debug = (argc >= 2 && std::string(argv[1]) == "--debug");
    int k, n;
    std::cin >> n >> k;

    std::vector<Element> elementy(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> elementy[i].wartosc;
        elementy[i].lewySasiad = (i > 0) ? i - 1 : -1;
        elementy[i].prawySasiad = (i < n - 1) ? i + 1 : -1;
    }

    std::set<std::pair<long long, int>, std::greater<std::pair<long long, int>>> zbior;

    for (int i = 0; i < n; ++i) {
        zbior.insert({elementy[i].wartosc, i});
    }

    long long wynik = 0;

    while (!zbior.empty()) {
        auto it = zbior.begin();
        long long wartoscX = it->first;
        int idxX = it->second;
        Element& x = elementy[idxX];

        if (x.lewySasiad != -1) {
            int lewyIdx = x.lewySasiad;
            Element& lewy = elementy[lewyIdx];
            long long staraWartosc = lewy.wartosc;
            if (wartoscX - k > staraWartosc) {
                long long diff = wartoscX - k - staraWartosc;
                wynik += diff;
                lewy.wartosc = wartoscX - k;
                zbior.erase({staraWartosc, lewyIdx});
                zbior.insert({lewy.wartosc, lewyIdx});
            }
        }

        if (x.prawySasiad != -1) {
            int prawyIdx = x.prawySasiad;
            Element& prawy = elementy[prawyIdx];
            long long staraWartosc = prawy.wartosc;
            if (wartoscX - k > staraWartosc) {
                long long diff = wartoscX - k - staraWartosc;
                wynik += diff;
                prawy.wartosc = wartoscX - k;
                zbior.erase({staraWartosc, prawyIdx});
                zbior.insert({prawy.wartosc, prawyIdx});
            }
        }

        zbior.erase({wartoscX, idxX});
    }

    std::cout << wynik << std::endl;

    return 0;
}