Submission #698141

#	Time	Username	Problem	Language	Result	Execution time	Memory
698141		hotboy2703	Safety (NOI18_safety)	C++14	100 / 100	53 ms	5376 KiB

safety

#include<bits/stdc++.h>
using namespace std;
long long n,h;
long long s[200100];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>h;
    for (long long i = 1;i <= n;i ++){
        cin>>s[i];
    }
    priority_queue <long long> l;
    priority_queue <long long,vector <long long> ,greater <long long> > r;
    long long add_l = 0,add_r = 0;
    long long ans = 0;
    long long pos = -1e18;
    for (long long i = 1;i <= n;i ++){
        add_l -= h;
        add_r += h;
        pos -= h;
        if (s[i] >= pos){
            ans += s[i];
            r.push(s[i]-add_r);
            r.push(s[i]-add_r);
            l.push(r.top()+add_r-add_l);
            r.pop();
            ans -= l.top() + add_l;

        }
        else{
            ans -= s[i];
            l.push(s[i]-add_l);
            l.push(s[i]-add_l);
            r.push(l.top()+add_l-add_r);
            l.pop();
            ans += r.top()+add_r;
        }
        assert(ans <= (long long)1e14);
        pos = l.top() + add_l;
    }
    cout<<ans<<'\n';
    return 0;
}

• 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