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
#include <cstdio>
#include <vector>
#include <algorithm>

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    std::vector<int> path;
    path.reserve(n);
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        path.push_back(x);
    }

    int adjust_amount = 0;
    auto pass = [&] (int begin, int end, int delta) {
        int mandatory_height = 0;
        for (int i = begin; i != end; i += delta) {
            mandatory_height = std::max(mandatory_height, path[i]);
            adjust_amount += mandatory_height - path[i];
            path[i] = mandatory_height;
            mandatory_height -= k;
        }
    };
    pass(0, n, 1);
    pass(n - 1, -1, -1);

    printf("%d\n", adjust_amount);

    return 0;
}