Submission #215987

#	Time	Username	Problem	Language	Result	Execution time	Memory
215987		dolphingarlic	Safety (NOI18_safety)	C++14	100 / 100	61 ms	7100 KiB

safety

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

ll a[200001];
priority_queue<ll> L, R;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    ll h;
    cin >> n >> h;
    FOR(i, 0, n) cin >> a[i];

    ll ans = 0;
    L.push(a[0]); R.push(-a[0]);
    FOR(i, 1, n) {
        ll X = L.top() - h * i, Y = -R.top() + h * i;
        if (X > a[i]) {
            ans += X - a[i];
            L.push(a[i] + h * i);
            L.push(a[i] + h * i);
            R.push(-X + h * i);
            L.pop();
        } else if (Y < a[i]) {
            ans += a[i] - Y;
            R.push(-a[i] + h * i);
            R.push(-a[i] + h * i);
            L.push(Y + h * i);
            R.pop();
        } else {
            L.push(a[i] + h * i);
            R.push(-a[i] + h * i);
        }
    }
    cout << ans;
    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 29 / 29