Submission #635660

#	Time	Username	Problem	Language	Result	Execution time	Memory
635660		PoonYaPat	Safety (NOI18_safety)	C++14	100 / 100	47 ms	5512 KiB

safety

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

int n,h,x;
ll ymin, shift;
priority_queue<ll> lsq;
priority_queue<ll, vector<ll>, greater<ll>> rsq; //fake value (has to adjust with shift)

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>h>>x;
    lsq.push(x);
    rsq.push(x);

    for (int i=1; i<n; ++i) {
        cin>>x;
        shift+=h;

        ll l=lsq.top()-shift, r=rsq.top()+shift; //real value

        if (x<=l) {
            lsq.push(x+shift);
            lsq.push(x+shift);

            rsq.push(lsq.top()-2*shift);
            lsq.pop();

            ymin+=(l-x);

        } else if (x>=r) {
            rsq.push(x-shift);
            rsq.push(x-shift);

            lsq.push(rsq.top()+2*shift);
            rsq.pop();

            ymin+=(x-r);
        } else {
            lsq.push(x+shift);
            rsq.push(x-shift);
        }
    }

    cout<<ymin;
}

• 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