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
import heapq

n, k = map(int, input().split())

road = list(map(int, input().split()))

heap = []

for idx, fragment in enumerate(road):
    heapq.heappush(heap, (-fragment, idx))

cnt = 0
while heap:
    _, idx = heapq.heappop(heap)
    curr_fragment_height = road[idx]

    if idx != 0 and road[idx-1] + k < curr_fragment_height:
        trucks_needed = curr_fragment_height - road[idx-1] - k
        cnt += trucks_needed
        road[idx-1] += trucks_needed
        heapq.heappush(heap, (-road[idx-1], idx-1))


    if idx != n - 1 and road[idx+1] + k < curr_fragment_height:
        trucks_needed = curr_fragment_height - road[idx+1] - k
        cnt += trucks_needed
        road[idx+1] += trucks_needed
        heapq.heappush(heap, (-road[idx+1], idx+1))

print(cnt)