Submission #349246

#	Time	Username	Problem	Language	Result	Execution time	Memory
349246		rivalq	Safety (NOI18_safety)	C++17	100 / 100	65 ms	5648 KiB

safety

// Jai Shree Ram  
  
#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,n)     for(int i=a;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC



template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}


int solve(){
		int n,h;cin>>n>>h;
		int ans=0;
		priority_queue<int>left;
		priority_queue<int,vector<int>,greater<int>>right;
		int x;cin>>x;
		left.push(x);
		right.push(x);
		rep(i,1,n){
			cin>>x;
			int shift = i*h;
			int l = left.top()-shift;
			int r = right.top()+shift;
			if(x<l){
				ans+=abs(x-l);
				left.pop();
				left.push(x+shift);
				left.push(x+shift);
				right.push(l-shift);
			}
			else if(x>r){
				ans+=abs(x-r);
				right.pop();
				right.push(x-shift);
				right.push(x-shift);
				left.push(r+shift);
			}
			else{
				left.push(x+shift);
				right.push(x-shift);
			}
		} 
		cout<<ans<<endl;
 return 0;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #ifdef SIEVE
    sieve();
    #endif
    #ifdef NCR
    init();
    #endif
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
    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