Submission #873114

#	Time	Username	Problem	Language	Result	Execution time	Memory
873114		imarn	Safety (NOI18_safety)	C++14	100 / 100	39 ms	6076 KiB

safety

#include<bits/stdc++.h>
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define f first
#define s second
#define vi vector<int>
#define vpii vector<pii>
#define ll long long
using namespace std;
priority_queue<ll,vector<ll>,greater<ll>>lq;
priority_queue<ll>rq;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;ll h;cin>>n>>h;
    ll ans=0;
    ll x;cin>>x;
    lq.push(x);
    rq.push(x);ans=0;
    for(ll i=1;i<n;i++){
        cin>>x;
        ll rl = i*h;
        ll rr = i*h;
        if(x-rl>lq.top()){
            lq.push(x-rl);
            ans+=(x-rl)-lq.top();
            lq.push(x-rl);
            rq.push(lq.top()+2*rl);
            lq.pop();
        }
        else if(x+rr<rq.top()){
            rq.push(x+rr);
            ans+=rq.top()-(x+rr);
            rq.push(x+rr);
            lq.push(rq.top()-rl-rr);
            rq.pop();
        }
        else {
            lq.push(x-rl);
            rq.push(x+rr);
        }
    }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