Submission #869512

#	Time	Username	Problem	Language	Result	Execution time	Memory
869512		kim	Safety (NOI18_safety)	C++17	100 / 100	42 ms	5488 KiB

safety

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll=long long;
#define pb push_back

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(0);
    
    int n; cin>>n;
    ll k; cin>>k;
    priority_queue<ll> pql;
    priority_queue<ll,vector<ll>,greater<ll>> pqr;
    ll x; cin>>x;
    pql.push(x),pqr.push(x);
    ll ans=0;
    for(int i=1;i<n;++i){
        cin>>x;
        ll y=i*k;
        if(x<pql.top()-y){
            ans+=abs(pql.top()-y-x);
            pql.push(x+y);
            pql.push(x+y);
            pqr.push(pql.top()-y-y);
            pql.pop();
        }
        else if(x>pqr.top()+y){
            ans+=abs(pqr.top()+y-x);
            pqr.push(x-y);
            pqr.push(x-y);
            pql.push(pqr.top()+y+y);
            pqr.pop();
        }
        else{
            pql.push(x+y);
            pqr.push(x-y);
        }
    }
    cout<<ans<<endl;
    
    return 0;
}
/*
6 7
1 2
2 3
3 1
2 4
4 5
5 6
6 5
*/

• 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