Submission #1165767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165767		tamyte	Swimming competition (LMIO18_plaukimo_varzybos)	C++17	100 / 100	480 ms	6376 KiB

plaukimo_varzybos

#include <bits/stdc++.h>



using namespace std;
using ll = long long;
vector<int> a;
int n, A, B;

bool ok(int m) {
	queue<int> q;
	q.push(-1);
	int i = A - 1;
	while (i < n && q.size()) {
		if (i - q.front() < A) {
			i++;
		} else {
			if (i - q.front() > B || a[i] - a[q.front() + 1] > m) {
				q.pop();
			} else {
				q.push(i);
				i++;
			}
		}
	}
	while (q.size() > 1) q.pop();
	return (q.size() && q.front() == n - 1);
}

int main() {
	cin >> n >> A >> B;
	a = vector<int>(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(begin(a), end(a));
	int l = 0, r = a[n - 1];
	// int c = 0;
	while (r - l > 0) {
		int m = (l + r) / 2;
		// cout << l << " " << r << endl;
		if (ok(m)) {
			r = m;
		} else {
			l = m + 1;
		}
	}
	cout << r << endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40