oj.uz

Submission #318635

# Submission time Handle Problem Language Result Execution time Memory
318635 2020-11-02T14:38:22 Z MetB Safety (NOI18_safety) C++14
18 / 100
 115 ms 6264 KB 
#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;

int 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]);

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

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

		if (a[i] < ltop) {
			lwing.push (a[i] + l), lwing.push (a[i] + l);
			rwing.push (ltop + r), lwing.pop ();
			ans += abs (a[i] - ltop);
		} else if (rtop < a[i]) {
			rwing.push (a[i] + r), rwing.push (a[i] + r);
			lwing.push (rtop + l), rwing.pop ();
			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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 5368 KB Output is correct
2 Correct 111 ms 6136 KB Output is correct
3 Correct 115 ms 6264 KB Output is correct

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -