Submission #1000720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000720		vjudge1	Safety (NOI18_safety)	C++17	100 / 100	165 ms	22548 KiB

safety

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll

int a[200100];

void solve(){
    int n, h;
    cin>>n>>h;
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }
    multiset<ll> ql, qr;
    ql.insert(a[1]);
    qr.insert(a[1]);
    ll ans = 0;
    for(int i=2; i<=n; i++){
        ll add = h * (i - 1);
        ll l=*ql.rbegin()-add, r=*qr.begin()+add;
        ll t = a[i];
        if(l <= t and t <= r){
            ql.insert(t+add);
            qr.insert(t-add);
        }
        else if(l > t){
            ans += l-t;
            qr.insert(l-add);
            ql.erase(ql.find(l + add));
            ql.insert(t+add);
            ql.insert(t+add);
        }
        else if(r < t){
            ans += t - r;
            ql.insert(r+add);
            qr.erase(qr.find(r - add));
            qr.insert(t-add);
            qr.insert(t-add);
        }
    } 
    cout<<ans<<'\n';
}



signed main(){
    solve();
}

• 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