Submission #172593

#	Time	Username	Problem	Language	Result	Execution time	Memory
172593		sjimed	Safety (NOI18_safety)	C++14	100 / 100	94 ms	7220 KiB

safety

#include<bits/stdc++.h>  
using namespace std;  
  
#define fast ios::sync_with_stdio(false);cin.tie(NULL)  
#define fi first  
#define se second  
#define all(v) (v).begin(),(v).end()  
#define pb push_back  
#define eb emplace_back
#define pre(a) cout<<fixed; cout.precision(a)
  
typedef long long ll;  
typedef pair<int,int> pii;  
typedef pair<ll,ll> pll;  
const long long INF = 1e18;  
const int inf = 1e9;

ll n, h, l, r, ans;
priority_queue<ll, vector<ll>, less<ll>> L;
priority_queue<ll, vector<ll>, greater<ll>> R;
ll arr[200010];

bool Swap() {
	ll x = L.top() + l;
	ll y = R.top() + r;

	if(x <= y) return false;
	ans += x - y;
	
	L.pop();
	R.pop();
	L.push(y - l);
	R.push(x - r);

	return true;
}

int main() {
	fast;

	cin >> n >> h;

	for(int i=0; i<n; i++) {
		l -= h;
		r += h;

		cin >> arr[i];

		L.push(arr[i] - l);
		R.push(arr[i] - r);

		while(Swap());
	}

	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