Submission #935996

#	Time	Username	Problem	Language	Result	Execution time	Memory
935996		ZeroCool	Safety (NOI18_safety)	C++14	100 / 100	210 ms	21052 KiB

safety

#define ONLINE_JUDGE // online judge
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
  
#define int long long
  
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
  
  
using ll = long long;
using ld = long double;
  
#define no cout<<"NO"<<endl
#define yes cout<<"YES"<<endl

#define da cout<<"DA"<<endl
#define ne cout<<"NE"<<endl
  
#define send ios::sync_with_stdio(false);
#define help cin.tie(0);
  
void solve(int T);
  
const int N = 505;
const int M = 405;
const int SQRT = sqrt(N);
const int LOG = 20;
const int INF = 1e12;
const int MOD = 998244353;
const ld EPS = 1e-9;
  
  
int ans;
int n, m, q, l, r, x, y, z, mx, mn;
  
  
int32_t main(){
    #ifndef ONLINE_JUDGE
        auto begin = chrono::high_resolution_clock::now();
    #endif
    cout<<setprecision(4)<<fixed;
      
    send help;
  
    int tt = 1;
//  cin>>tt; //? Comment if no testcases
    for(int i = 1;i<=tt;i++){
        #ifndef ONLINE_JUDGE
            cout<<"Case "<<i<<": "<<endl;
        #endif
        solve(i);
    }
    #ifndef ONLINE_JUDGE
        auto end = chrono::high_resolution_clock::now();
        cout<<"Time: "<<chrono::duration_cast<chrono::duration<double>>(end - begin).count()<<endl;
    #endif
    return 0;
}

multiset<int> lefts, rights;


void solve(int T){
    int h;
    cin>>n>>h;
    int x;
    cin>>x;
    lefts.insert(x);
    rights.insert(x);
    int loff = -h, roff = h;
    for(int i = 1;i<n;i++){
        cin>>x;
        l = *lefts.rbegin() + loff;
        r = *rights.begin() + roff;
        if(l >= x){
            ans += l - x;
            rights.insert(l - roff);
            lefts.erase(lefts.find(*lefts.rbegin()));
            lefts.insert(x - loff);
            lefts.insert(x - loff);

        }else if (r >= x){
            lefts.insert(x - loff);
            rights.insert(x - roff);
        }else{
            ans += x - r;
            lefts.insert(r - loff);
            rights.erase(rights.find(*rights.begin()));
            rights.insert(x - roff);
            rights.insert(x - roff);
        }
        loff -= h;
        roff += h;
    }    
    cout<<ans<<endl;
}   

  
  
  
//Te molam da raboti!!

• 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