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
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<int> heights(n);
    for(auto &a : heights)
        cin >> a;
    
    int result = 0;
    for(int i=1; i<n; i++) {
        if(heights[i-1] - heights[i] > k) {         //increase just here
            result += heights[i-1] - heights[i] - k;
            heights[i] = heights[i-1] - k;
        }
        else if(heights[i] - heights[i-1] > k) {            //need to increase earlier spots
            for(int j=i-1; j>=0 && heights[j+1] - heights[j] > k; j--) {
                result += heights[j+1] - heights[j] - k;
                heights[j] = heights[j+1] - k;
            }
        }
    }
    cout << result << "\n";

    return 0;
}