Submission #470090

#	Time	Username	Problem	Language	Result	Execution time	Memory
470090		definitelynotmee	Safety (NOI18_safety)	C++98	100 / 100	262 ms	20652 KiB

safety

#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
template <typename T>
using matrix = vector<vector<T>>;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6+1;



int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, h;
    cin >> n >> h;
    vector<ll> v(n);
    for(int i = 0; i < n; i++)
        cin >> v[i];
    
    ll offsetl = 0, offsetr = 0;
    ll resp = 0;
    multiset<ll,greater<ll>> left;
    multiset<ll> right;
    left.insert(v[0]);
    right.insert(v[0]);
    for(int i = 1; i < n; i++){

        offsetl-=h;
        offsetr+=h;
        pll last = {*left.begin()+offsetl,*right.begin()+offsetr};
        if(v[i]<= last.ff){
            left.insert(v[i]-offsetl), left.insert(v[i]-offsetl), right.insert(*left.begin()+offsetl-offsetr), left.erase(left.begin());
            resp += last.ff-v[i];
        }else right.insert(v[i]-offsetr), right.insert(v[i]-offsetr), left.insert(*right.begin()+offsetr-offsetl), right.erase(right.begin()), resp += max(0ll,v[i]-last.ss);

    }
    cout << resp << '\n';
 
    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