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
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    int n;
    int64_t k;
    cin >> n >> k;
    vector<pair<int, int64_t>> t(n);
    for (int i = 0; i < n; i++)
    {
        cin >> t[i].first;
        t[i].second = i;
    }
    sort(t.begin(), t.end(), greater<pair<int, int64_t>>());
    map<int, int64_t> result;
    int64_t cost = 0;
    for (auto p : t)
    {
        result[p.second] = p.first;
        auto it = result.find(p.second);

        if (it != result.begin())
        {
            auto previous = prev(it);
            int pos = previous->first;
            int64_t val = previous->second;
            int64_t diff = val - (it->second) - k * (p.second - pos);
            if (diff > 0)
            {
                cost += diff;
                it->second += diff;
            }
        }
        auto right = next(it);
        if (right != result.end())
        {
            int pos = right->first;
            int64_t val = right->second;
            int64_t diff = val - (it->second)- k * (pos - p.second);
            if (diff > 0)
            {
                cost += diff;
                it->second += diff;
            }
        }
    }

    cout << cost << "\n";
}