Submission #1184131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184131		Namkhing	Safety (NOI18_safety)	C++20	100 / 100	33 ms	5212 KiB

safety

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

using ll = long long;

const int N = 2e5 + 10;
ll n, h, ans, lzl, lzr, a[N];
priority_queue<ll> pql;
priority_queue<ll, vector<ll>, greater<ll>> pqr;

int main() {
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    cin >> n >> h;
    for (int i = 1; i <= n; i++) cin >> a[i];
    pql.push(a[1]);
    pqr.push(a[1]);
    for (int i = 2; i <= n; i++) {
        lzl += h;
        lzr += h;
        if (a[i] < pql.top() - lzl) {
            ll x = pql.top(); pql.pop();
            ans += x - lzl - a[i];
            pqr.push(x - lzl - lzr);
            pql.push(a[i] + lzl);
            pql.push(a[i] + lzl);
        }
        else if (a[i] > pqr.top() + lzr) {
            ll x = pqr.top(); pqr.pop();
            ans += a[i] - x - lzr;
            pql.push(x + lzl + lzr);
            pqr.push(a[i] - lzr);
            pqr.push(a[i] - lzr);
        }
        else {
            pql.push(a[i] + lzl);
            pqr.push(a[i] - lzr);
        }
    }
    cout << ans;
}

• 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