Submission #73262315

---

Source Code Expand

#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ul = unsigned long;
using ld = long double;
using bl = bool;
using st = string;
using mint = atcoder::modint998244353;
using Mint = atcoder::modint1000000007;

#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>
#define vvvvl vector<vvvl>

#define vd vector<ld>
#define vvd vector<vd>
#define vvvd vector<vvd>
#define vvvvd vector<vvvd>

#define vb vector<bl>
#define vvb vector<vb>
#define vvvb vector<vvb>
#define vvvvb vector<vvvb>

#define vs vector<st>
#define vvs vector<vs>
#define vvvs vector<vvs>

#define vp vector<pair<ll, ll>>
#define vvp vector<vp>
#define vvvp vector<vvp>

#define vm vector<mint>
#define vvm vector<vm>
#define vvvm vector<vvm>

#define vM vector<Mint>
#define vvM vector<vM>
#define vvvM vector<vvM>

#define cmx(n, v) n = n < v ? v : n
#define cmn(n, v) n = n > v ? v : n

#define all(n) begin(n), end(n)
#define nxp(a) next_permutation(all(a))
#define rev(n) reverse(all(n))
#define sor(n) stable_sort(all(n))

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, n) for (ll i = a; i < (n); i++)
#define rep3(i, n) for (ll i = n - 1; i >= 0; i--)

#define sz(n) n.size()

#define lb(vec, src) lower_bound(vec.begin(), vec.end(), src) - vec.begin()
#define ub(vec, src) upper_bound(vec.begin(), vec.end(), src) - vec.begin()
#define lb2(vec, src) *lower_bound(vec.begin(), vec.end(), src)
#define ub2(vec, src) *upper_bound(vec.begin(), vec.end(), src)

#define mn1(a) min_element(all(a))
#define mx1(a) max_element(all(a))
#define mn2(a) *min_element(all(a))
#define mx2(a) *max_element(all(a))

#define uniq(a)                                                                \
    {                                                                          \
        sort(all(a));                                                          \
        (a).erase(unique(all(a)), (a).end());                                  \
    }

#define DET2(x1, y1, x2, y2) (x1) * (y2) - (x2) * (y1)
#define DET3(x1, y1, z1, x2, y2, z2, x3, y3, z3)                               \
    (x1) * (y2) * (z3) + (x2) * (y3) * (z1) + (x3) * (y1) * (z2) -             \
        (z1) * (y2) * (x3) - (z2) * (y3) * (x1) - (z3) * (y1) * (x2)
const ll inf = 9e18;

ll calc_digit(ll N) {
    ll res = 0;
    while (N > 0) {
        res++;
        N /= 10;
    }
    return res;
}

ll factorial(ll n, ll mod = 1e18) {
    ll ans = 1;
    for (ll i = n; i >= 2; i--)
        ans = (ans * i) % mod;
    return ans;
}

ll floor_int(ll x, ll m) {
    ll r = (x % m + m) % m; // 負の剰余を正の剰余に置き換える
    return (x - r) / m;     // return
}

ll round_up(ll x, ll y) {
    ll res = (x + y - 1) / y;
    return res;
}

ll rmd(ll x, ll m) {
    ll r = (x % m + m) % m; // 負の剰余を正の剰余に置き換える
    return r;
}

ll rmd_2(ll x, ll m) {
    ll r = (x % m + m) % m; // 負の剰余を正の剰余に置き換える
    return (m - r) % m;     // return
}

ll bubble_sort(vl a, ll n) {
    ll res = 0;
    rep(i, n - 1) {
        for (ll j = n - 1; j > i; j--) {
            if (a[j - 1] > a[j]) {
                swap(a[j - 1], a[j]);
                res++;
            }
        }
    }
    return res;
}

ll sum_v(vl a) {
    ll res = 0;
    ll n = sz(a);
    rep(i, n) res += a[i];
    return res;
}

ll stair_sum(ll from, ll to) { return (from + to) * (to - from + 1) / 2; }

ll Power(ll var, ll p) {
    if (p == 1)
        return var;
    ll ans = Power(var * var, p / 2);
    if (p & 1)
        ans *= var;
    return ans;
}

ll cnt_01(ll n, ll now) {
    ll res = 0;
    res += (n / now) * (now / 2);
    if (n % now >= now / 2)
        res += n % now - (now / 2) + 1;
    return res;
}

ll sum_pop(ll n) {
    ll res = 0;
    for (ll b = 0; b < 60; b++) {
        res += (n / (1ll << (b + 1))) * (1ll << b);
        res += max(0ll, n % (1ll << (b + 1)) - (1ll << b) + 1);
    }
    return res;
}

ll Tree_Diameter(vvl &g) {
    ll n = sz(g);
    ll start = 0;
    ll ans = 0;
    for (ll i = 0; i < 2; i++) {
        queue<ll> q;
        q.push(start);
        vl dis(n, inf);
        dis[start] = 0;
        while (!q.empty()) {
            ll u = q.front();
            q.pop();
            start = u;
            ans = dis[u];
            for (ll v : g[u]) {
                if (dis[v] != inf)
                    continue;
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    return ans;
}

ll calc_sum_of_abs_dis(vl a) {
    sor(a);
    ll n = sz(a);
    ll res = 0;
    rep(i, n) res += a[i] * (2 * i + 1 - n);
    return res;
}

bool is_prime(ll N) {
    if (N == 1)
        return false;
    if (N == 2)
        return true;
    if (N % 2 == 0)
        return false;
    for (ll p = 3; p * p <= N; p += 2)
        if (N % p == 0)
            return false;
    return true;
}

bool in_out(ll x, ll y, ll h, ll w) {
    return 0 <= x and x < h and 0 <= y and y < w;
}

bool dis_solve1(ll x1, ll x2, ll y1, ll y2, ll r) {
    ll xx = (x1 - x2), yy = (y1 - y2);
    ll dis = xx * xx + yy * yy;
    return (r * r == dis);
}

bool dis_solve2(ll x1, ll x2, ll y1, ll y2, ll d1, ll d2) {
    ll xx = (x1 - x2), yy = (y1 - y2), r1 = (d1 + d2), r2 = (d1 - d2);
    ll dis = xx * xx + yy * yy;
    return (r2 * r2 <= dis && dis <= r1 * r1);
}

void printl(vl v, ll len = 0) {
    ll vsz = min(len, ll(v.size()));
    for (ll i = 0; i < vsz; i++) {
        cout << v[i] << endl;
    }
}

void prints(vs v) {
    ll vsz = v.size();
    for (ll i = 0; i < vsz; i++) {
        cout << v[i] << endl;
    }
}

vl p_list(ll n) {
    vl res;
    vb check(n + 1);
    for (ll i = 2; i <= n; i++) {
        if (check[i])
            continue;
        res.push_back(i);
        ll ii = i;
        while (ii <= n) {
            check[ii] = true;
            ii += i;
        }
    }
    return res;
}

vl cumulative_sum(vl a) {
    ll s = sz(a);
    vl b(s + 1, 0);
    for (ll i = 0; i < s; i++) {
        b[i + 1] = a[i] + b[i];
    }
    return b;
}

vl n_num(ll a, ll n) {
    vl res;
    while (a) {
        res.push_back(a % n);
        a /= n;
    }
    rev(res);
    return res;
}

vl c_press(vl a) {
    ll n = sz(a);
    vl res = a, c = a;
    sor(c);
    uniq(c);
    rep(i, n) res[i] = lb(c, res[i]);
    return res;
}

vl min_fact(ll n) {
    vl pl;
    vl res(n + 1, -1);
    for (ll d = 2; d <= n; d++) {
        if (res[d] == -1) {
            res[d] = d;
            pl.push_back(d);
        }
        for (ll p : pl) {
            if (p * d > n || p > res[d])
                break;
            res[p * d] = p;
        }
    }
    return res;
}

vvl to_grid(vl &a, ll k) {
    ll n = sz(a);
    ll m = (n + k - 1) / k;
    vvl b(k, vl(m, inf));
    rep(i, n) b[i % k][i / k] = a[i];
    return b;
}

vvl rotate_ll(vvl &V2d, ll wise) {
    vvl a = V2d;
    ll h = sz(a), w = sz(a[0]);
    vvl res(w, vl(h));
    if (wise) {
        rep(i, h) rep(j, w) res[j][h - i - 1] = a[i][j];
    } else {
        rep(i, h) rep(j, w) res[w - j - 1][i] = a[i][j];
    }
    return res;
}

vs rotate_st(vs s, ll wise) {
    vs a = s;
    ll h = sz(a), w = sz(a[0]);
    vs res(w);
    rep(i, w) res[i].append(h, '.');
    if (wise) {
        rep(i, h) rep(j, w) res[j][h - i - 1] = a[i][j];
    } else {
        rep(i, h) rep(j, w) res[w - j - 1][i] = a[i][j];
    }
    return res;
}

vp prime_factorize(ll N) {
    vp res;
    for (ll a = 2; a * a <= N; ++a) {
        if (N % a != 0)
            continue;
        ll ex = 0;
        while (N % a == 0) {
            ex++;
            N /= a;
        }
        res.push_back({a, ex});
    }
    if (N != 1)
        res.push_back({N, 1});
    return res;
}

vector<pair<ll, ll>> RLEint(vl a) {
    ll n = sz(a);
    vector<pair<ll, ll>> res;
    res.push_back({a[0], 1});
    for (ll i = 1; i < n; i++) {
        if (res.back().first != a[i]) {
            res.push_back({a[i], 1});
        } else {
            res.back().second++;
        }
    }
    return res;
}

vector<pair<char, ll>> RLEchar(st s) {
    ll n = sz(s);
    vector<pair<char, ll>> res;
    res.push_back({s[0], 1});
    for (ll i = 1; i < n; i++) {
        if (res.back().first != s[i]) {
            res.push_back({s[i], 1});
        } else {
            res.back().second++;
        }
    }
    return res;
}

template <typename T> void input(T &a) { cin >> a; };
template <typename T1, typename... T2> void input(T1 &a, T2 &...b) {
    cin >> a;
    input(b...);
};

template <typename T = ll> vector<T> rd(size_t n) {
    vector<T> ts(n);
    for (size_t i = 0; i < n; i++)
        cin >> ts[i];
    return ts;
}

ll di[8] = {1, -1, 0, 0, 1, 1, -1, -1};
ll dj[8] = {0, 0, 1, -1, 1, -1, -1, 1};

// abcdefghijklmnopqrstuvwxyz
// std::setprecision(15);
// 2^29<10^9

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    ll n, k;
    cin >> n >> k;
    vl a = rd(n);
    vl pre = a;

    for (ll i = 1; i < n; i++) {
        a[i] = max(a[i], a[i - 1] - k);
    }

    for (ll i = n - 2; i >= 0; i--) {
        a[i] = max(a[i], a[i + 1] - k);
    }

    ll ans = 0;
    rep(i, n) { ans += a[i] - pre[i]; }

    cout << ans << endl;
}

Submission Info

Judge Result