Submission #1251524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251524		DanielPr8	Safety (NOI18_safety)	C++20	100 / 100	160 ms	18984 KiB

safety

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using vb = vector<bool>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()

int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    ll n, h;
    cin >> n >> h;
    ll ans=0,pl=0;
    multiset<ll> l, r;
    for(ll a,i = 0; i < n; ++i){
        cin >> a;
        a+=h*i;
        pl+=h*2;
        if(l.empty() || a<=*(l.rbegin())){
            l.insert(a);
            l.insert(a);
            ll o = *(l.rbegin());
            r.insert(o-pl);
            l.erase(l.find(o));
            ans += o-a;
        }
        else{
            r.insert(a-pl);
            r.insert(a-pl);
            ll o = *(r.begin());
            l.insert(o+pl);
            r.erase(r.begin());
            ans += a-o-pl;
        }
    }
    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