Submission #318636

#	Time	Username	Problem	Language	Result	Execution time	Memory
318636		MetB	Safety (NOI18_safety)	C++14	100 / 100	123 ms	7164 KiB

safety

#include <bits/stdc++.h>
 
#define N 2000001
 
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
 
const ll INF = 1e18, MOD = 998244353, MOD2 = 1e6 + 3;

ll s, e, h, n, a[N];

priority_queue<ll, vector<ll>> lwing;
priority_queue<ll, vector<ll>, greater<ll>> rwing;

ll solve (string testname) {
	lwing.push (a[0]);
	rwing.push (a[0]);

	ll l = 0, r = 0;
	ll ans = 0;

	for (int i = 1; i < n; i++) {
		l += h, r -= h;
		ll ltop = lwing.top () - l;
		ll rtop = rwing.top () - r;

		if (a[i] < ltop) {
			lwing.pop ();
			lwing.push (a[i] + l), lwing.push (a[i] + l);
			rwing.push (ltop + r);
			ans += abs (a[i] - ltop);
		} else if (rtop < a[i]) {
			rwing.pop ();
			rwing.push (a[i] + r), rwing.push (a[i] + r);
			lwing.push (rtop + l);
			ans += abs (a[i] - rtop);
		} else {
			lwing.push (a[i] + l);
			rwing.push (a[i] + r);
		}
	}

	return ans;
}

int main () {
	/*cin >> s >> e >> h;
	mt19937 rng;
	n = 300;

	while (s <= e) {
		string testname = "test_" + to_string (s++);
		ofstream fout (testname + ".in");
		int lh = uniform_int_distribution<int>(h / 10, max ((int) 1e9, 10 * h))(rng);
		fout << n << '\n' <<  << '\n';
		for (int i = 0; i < n; i++) {
			a[i] = uniform_int_distribution<int>(1, 1000000000)(rng);
			fout << a[i] << ' ';
		}
		fout << endl;
		fout.close ();

	}*/

	cin >> n >> h;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	cout << solve ("");
}

• 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