Submission #924402

#	Time	Username	Problem	Language	Result	Execution time	Memory
924402		pcc	Safety (NOI18_safety)	C++14	100 / 100	175 ms	20976 KiB

safety

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


ll rs = 0,ls = 0,ans = 0;
multiset<ll> lst,rst;
ll N,H;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>H;
	int k;
	cin>>k;
	lst.insert(k);
	rst.insert(k);
	ls = -H,rs = H;
	for(int i = 2;i<=N;i++){
		ll k;
		cin>>k;
		ll lx = *lst.rbegin()+ls,rx = *rst.begin()+rs;
		if(lx>=k){
			ans += lx-k;
			rst.insert(lx-rs);
			lst.erase(lst.find(*lst.rbegin()));
			lst.insert(k-ls);
			lst.insert(k-ls);
		}
		else if(rx>=k){
			lst.insert(k-ls);
			rst.insert(k-rs);
		}
		else{
			ans += k-rx;
			lst.insert(rx-ls);
			rst.erase(rst.find(*rst.begin()));
			rst.insert(k-rs);
			rst.insert(k-rs);
		}
		ls -= H,rs += H;
	}
	cout<<ans;
}

• 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