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

using int64 = long long int;

int main()
{
    int n, k;
    std::cin >> n >> k;
    std::vector<int> h(n);
	std::vector<int> order(n);
    for (int i = 0; i < n; ++i)
    {
		std::cin >> h[i];
        order[i] = i;
    }
    std::sort(order.begin(), order.end(), [&h](const int a, const int b) { return h[a] > h[b]; });
    std::vector<bool> visited(n, false);
    int64 added = 0;
    auto walk = [&](int index, const int direction, int height) -> void
	{
		while (0 <= index && index < n)
        {
            if (h[index] + k >= height) break;
			const int add = height - (h[index] + k);
			h[index] += add;
            height = h[index];
            added += add;
            index += direction;
        }
	};
    for (int i = 0; i < n; ++i)
    {
        const int index = order[i];
        if (!visited[index])
        {
            const int height = h[index];
            walk(index - 1, -1, height);
            walk(index + 1, 1, height);
        }
    }
    std::cout << added;
    return 0;
}

/*

4 2
7 3 0 2

*/