제출 #1199569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199569		sofapuden	Safety (NOI18_safety)	C++20	100 / 100	131 ms	19168 KiB

safety

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll n, h; cin >> n >> h;
	multiset<ll> L, R;
	priority_queue<ll> mer;
	ll dl = 0, dr = 0;
	ll ans = 0;
	for(int i = 0; i < n; ++i){
		int x; cin >> x;
		ans -= x;
		L.insert(x - dl);
		R.insert(x - dr);
		while(*R.begin() + dr < *L.rbegin() + dl){
			R.insert(*L.rbegin() + dl - dr);
			L.insert(*R.begin() + dr - dl);
			R.erase(R.begin());
			L.erase(prev(L.end()));
		}
		ans -= (i + 1) * h;
		dl -= h;
		dr += h;
	}
	for(auto x : R)ans += x + dr;
	cout << ans << '\n';
}

• 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