Submission #1060363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060363		idas	Safety (NOI18_safety)	C++17	100 / 100	38 ms	7036 KiB

safety

#include "bits/stdc++.h"
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) ((int)(x).size())
#define pb push_back
#define s second
#define f first

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N=2e5+10;
ll n, h, a[N];
priority_queue<ll> l;
priority_queue<ll, vector<ll>, greater<ll>> r;

int main() {
    FAST_IO;
    cin >> n >> h;
    FOR(i, 0, n) cin >> a[i];
    l.push(a[0]); r.push(a[0]);
    ll add=h, ans=0;
    FOR(i, 1, n) {
        if(a[i]>r.top()+add) {
            ll tp=r.top(); r.pop();
            tp+=add;
            ans+=a[i]-tp;
            tp+=add;
            l.push(tp);
            r.push(a[i]-add);
            r.push(a[i]-add);
        }
        else if(a[i]<l.top()-add) {
            ll tp=l.top(); l.pop();
            tp-=add;
            ans+=tp-a[i];
            tp-=add;
            r.push(tp);
            l.push(a[i]+add);
            l.push(a[i]+add);
        }
        else {
            l.push(a[i]+add);
            r.push(a[i]-add);
        }
        add+=h;
    }
    cout << ans;
}
/*
2 1
3 7

4 1
4 3 2 1
*/

• 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