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

using namespace std;

const int M = 10000;
int a[M] = {};
int dos[M] = {};
bool v[M] = {};
int n,k;

int obecnie(int j) {
    return a[j]+dos[j];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int i;
    cin>>n>>k;
    for (i=1; i <= n; i++)
        cin>>a[i];
    
    int Max = 0;
    a[Max] = -1;
    dos[Max] = -1;

    for (i=1; i <= n; i++) {
        Max = 0;
        for (int j=1; j <= n; j++)
            if ((a[j]+dos[j])>(a[Max]+dos[Max]) && !v[j])
                Max = j;
        v[Max] = true;
        if (Max>1) dos[Max-1] = max(obecnie(Max) - k, obecnie(Max-1)) - a[Max-1];
        if (Max<n) dos[Max+1] = max(obecnie(Max) - k, obecnie(Max+1)) - a[Max+1];
    }

    int sum = 0;
    for (i=1; i <= n; i++) {
        sum += dos[i];
    }
    cout << sum << '\n';

    return 0;
}