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
#include <iostream>
#include <set>
#include <vector>
using namespace std;

vector<int> v;
multiset<pair<int, int>> m;
int ilosc_potrzebnego_zwiru = 0;

void ryan_gosling(int idx, int wymagana_minimalna_wys) {
    if(v[idx] >= wymagana_minimalna_wys)
        return;

    ilosc_potrzebnego_zwiru += wymagana_minimalna_wys - v[idx];
    m.erase(m.find({v[idx], idx}));
    v[idx] = wymagana_minimalna_wys;
    m.emplace(wymagana_minimalna_wys, idx);
}

int main() {
    int n, k;
    cin >> n >> k;
    
    v.reserve(n);
    
    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        v.emplace_back(a);
        m.emplace(a, i);
    }

    while(m.size()) {
        auto [wys, idx] = *m.rbegin();
        m.erase(std::prev(m.end()));
        int wymagana_minimalna_wys = wys - k;
        if(idx >= 1) {
            ryan_gosling(idx-1, wymagana_minimalna_wys);
        } 
        if(idx <= n-2) {
            ryan_gosling(idx+1, wymagana_minimalna_wys);
        }
    }

    cout << ilosc_potrzebnego_zwiru << "\n";

    return 0;
}