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

typedef std::pair<int, int> Para;

int main() {
    int dlugosc;
    int stopien;

    scanf("%d %d", &dlugosc, &stopien);

    std::vector<int> wysokosc;
    wysokosc.reserve(dlugosc);
    std::priority_queue<Para> kolejka;

    for (int i=0; i< dlugosc; ++i) {
        int fragment;
        scanf("%d", &fragment);
        wysokosc.emplace_back(fragment);
        kolejka.emplace(fragment, i);
    }

    long long ciezarowek = 0;

    while (! kolejka.empty()) {
        const Para &para = kolejka.top();
        int szczyt = para.first;
        int i = para.second;
        kolejka.pop();
        //fprintf(stderr, "> fr. %d wys.%d \n", i, szczyt);
        if (0 <= i-1) {
            if (wysokosc[i-1] < szczyt-stopien) {
                int dosypanych = szczyt-stopien - wysokosc[i-1];
                ciezarowek += dosypanych;
                //fprintf(stderr, "  dos. fr. %d wys.%d + %d \n", i-1, wysokosc[i-1], dosypanych);
                wysokosc[i-1] += dosypanych;
                kolejka.emplace(wysokosc[i-1], i-1);
            }
        }
        if (i+1 < dlugosc) {
            if (wysokosc[i+1] < szczyt-stopien) {
                int dosypanych = szczyt-stopien - wysokosc[i+1];
                ciezarowek += dosypanych;
                //fprintf(stderr, "  dos. fr. %d wys.%d + %d \n", i+1, wysokosc[i+1], dosypanych);
                wysokosc[i+1] += dosypanych;
                kolejka.emplace(wysokosc[i+1], i+1);
            }
        }
    }

    printf("%lld\n", ciezarowek);
}