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

using ll = long long;

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

    int kawalki;
    ll luzik;
    cin >> kawalki >> luzik;

    vector<ll> pagorek(kawalki + 2), zlewka(kawalki + 2), prawa_bieda(kawalki + 2), finalny_syf(kawalki + 2);

    for (int i = 1; i <= kawalki; i++) cin >> pagorek[i];

    zlewka[1] = pagorek[1];
    for (int i = 2; i <= kawalki; i++) {
        zlewka[i] = max(pagorek[i], zlewka[i - 1] - luzik);
    }

    prawa_bieda[kawalki] = pagorek[kawalki];
    for (int i = kawalki - 1; i >= 1; i--) {
        prawa_bieda[i] = max(pagorek[i], prawa_bieda[i + 1] - luzik);
    }

    ll wynikowy_zwirek = 0;

    for (int i = 1; i <= kawalki; i++) {
        finalny_syf[i] = max(zlewka[i], prawa_bieda[i]);
        wynikowy_zwirek += finalny_syf[i] - pagorek[i];
    }

    cout << wynikowy_zwirek << '\n';
    return 0;
}