Submission #476144

#	Time	Username	Problem	Language	Result	Execution time	Memory
476144		thiago_bastos	Watching (JOI13_watching)	C++17	0 / 100	1 ms	332 KiB

watching

#include "bits/stdc++.h"

using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;

int n, p, q;
vector<int> a;

bool part(int w) {
	int i, j, P, Q;
	
	P = Q = i = j = 0;
	
	for(int k = 0; k < n; ++k) {
		while(i < n && a[i] < a[k] + w) ++i;
		while(j < n && a[j] < a[k] + 2LL * w) ++j;
		if(i == j) {
			if(P < p) {
				++P;
				k = i - 1;
			} else {
				++Q;
				k = j - 1;
			}
		} else {
			if(a[j - 1] < a[k] + 2LL * w) {
				if(Q < q) {
					++Q;
					k = j - 1;
				} else {
					++P;
					k = i - 1;
				}
			} else {
				if(P < p) {
					++P;
					k = i - 1;
				} else {
					++Q;
					k = j - 1;
				}
			}
		}
	}
	return P <= p && Q <= q;
}

void solve() {
	
	cin >> n >> p >> q;
	
	a.resize(n);
	
	for(int& v : a) cin >> v;
	
	sort(a.begin(), a.end());
	
	int lo = 1, hi = 1e9;
	
	while(lo < hi) {
		int mid = (lo + hi) / 2;
		if(part(mid)) hi = mid;
		else lo = mid + 1;
	}
	
	cout << hi << '\n';
}	

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
 	return 0;
}

• Subtask 1: 0 / 50
• Subtask 2: 0 / 50