oj.uz

Submission #476145

# Submission time Handle Problem Language Result Execution time Memory
476145 2021-09-25T02:52:17 Z thiago_bastos Watching (JOI13_watching) C++17
0 / 100
 2 ms 204 KB 
#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 {
			bool flag = i < n && j < n && a[j] - a[i] < w;
						
			if(!flag) {
				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());
	a.resize(unique(a.begin(), a.end()) - a.begin());
	n = a.size();
	
	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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Incorrect 0 ms 204 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

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