Submission #738424

#	Time	Username	Problem	Language	Result	Execution time	Memory
738424		peteza	Safety (NOI18_safety)	C++14	100 / 100	56 ms	3628 KiB

safety

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

ll n, h, x, i;
ll miny = 0, lzl, lzr;
priority_queue<ll> l;
priority_queue<ll, vector<ll>, greater<ll>> r;

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> h;
    for(i=0;i<n;i++) {
        cin >> x;
        if(l.empty() || r.empty()) {
            l.push(x); r.push(x);
        } else {
            if(x <= l.top()+lzl) {
                miny += l.top() + lzl - x;
                l.push(x-lzl); l.push(x-lzl); r.push(l.top()+lzl-lzr); l.pop();
            } else if(r.top() + lzr <= x) {
                miny += x - (r.top() + lzr);
                r.push(x-lzr); r.push(x-lzr); l.push(r.top()+lzr-lzl); r.pop();
            } else {
                l.push(x-lzl); r.push(x-lzr);
            }
        }
        lzl -= h; lzr += h;
    }
    cout << miny;
}

• 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