Submission #1363179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1363179		erering	Safety (NOI18_safety)	C++20	100 / 100	150 ms	20712 KiB

safety

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pb push_back
const int N=1e5+5,MAXA=1e6+5,inf=2e9+5,MOD=982451653;
multiset<int> lef,rig;
int mn,shl=0,shr=0;
void insert(int A){
    if (A >= *rig.begin()+shr) {
        mn += A - (*rig.begin()+shr);
        lef.insert(*rig.begin()+shr-shl);
        rig.extract(rig.begin());
        rig.insert(A-shr);
        rig.insert(A-shr);
    }
    else if (A <= *lef.rbegin()+shl) {
        mn += *lef.rbegin()+shl - A;
        rig.insert(*lef.rbegin()+shl-shr);
        lef.extract(*lef.rbegin());
        lef.insert(A-shl);
        lef.insert(A-shl);
    }
    else {
        lef.insert(A-shl);
        rig.insert(A-shr);
    }
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //dp[x]->min(-inf,x-1), dp[x]+=abs(x-a[i])
    int n,h; cin>>n>>h;
    int a[n];
    lef.insert(-inf); rig.insert(inf);
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(i==0){
            mn=0;
            lef.insert(a[i]); rig.insert(a[i]);
        }
        else{
            shr+=h; shl-=h;
            insert(a[i]);
        }
    }
    cout<<mn;
}

• 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