Submission #698038

#	Time	Username	Problem	Language	Result	Execution time	Memory
698038		hotboy2703	Safety (NOI18_safety)	C++17	100 / 100	208 ms	22540 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];
    }
    multiset <long long> l,r;
    long long add_l = 0,add_r = 0;
    long long a = 0, b = 0;
    for (long long i = 1;i <= n;i ++){
        add_l -= h;
        add_r += h;
        b += h * a;
        a--;
        b += s[i];
        l.insert(s[i] - add_l);
        l.insert(s[i] - add_l);
        while (!r.empty() && *l.rbegin() + add_l > *r.begin() + add_r){
            long long tmp = *l.rbegin() + add_l;
            l.erase(l.find(*l.rbegin()));
            r.insert(tmp - add_r);
        }
        while (l.size() > r.size()){
            long long tmp = *l.rbegin() + add_l;
           l.erase(l.find(*l.rbegin()));
            r.insert(tmp - add_r);
        }
        while (r.size() > l.size()){
            long long tmp = *r.begin() + add_r;
            r.erase(r.find(*r.begin()));
            l.insert(tmp - add_l);
        }
    }
    for (auto x:l){
        x += add_l;
        a++;
        b -= x;
        if (a == 0){
            cout<<b<<'\n';
            return 0;
        }
    }
    for (auto x:r){
        x += add_r;
        a++;
        b -= x;
        if (a == 0){
            cout<<b<<'\n';
            return 0;
        }
    }
    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