oj.uz

Submission #252424

# Submission time Handle Problem Language Result Execution time Memory
252424 2020-07-25T14:33:05 Z c4ts0up Watching (JOI13_watching) C++17
0 / 100
 2 ms 384 KB 
/*
ID: 
LANG: C++
TASK: 
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define ff first
#define ss second

const int NMAX = 2e3+2, PMAX = 1e5+2;

ll n, p, q;
vector <ll> arr;

/*//
bool Check(ll w) {
	int i=0, pres=p, qres=q, j;
	
	while (i<n) {
		// no podemos continuar
		if (!qres && !pres) return false;
		
		// podemos tomar uno largo
		if (qres) {
			while (j+1<n && arr[j+1]-arr[i]+1 <= 2*w) j++
		}
	}
}
//*/

bool Check(ll w) {
	int i = 0, pres = p, qres = q, j;
	
	//cerr << "---" << endl << "w = " << w << endl;
	while (i<n) {
		//cerr << "i = " << i << "; pres = " << pres << "; qres = " << qres;
		j = i;
		while (j+1<n && arr[j+1]-arr[i]+1<=w) j++;
		
		// revisa si el siguiente elemento está en el rango deseado
		if (j+1<n && arr[j+1]-arr[i]+1<=2*w) {
			while (j+1<n && arr[j+1]-arr[i]+1<=2*w) j++;
		}
		
		//cerr << "; j = " << j << endl;
		
		// si debemos usar una q
		if (w < arr[j]-arr[i]+1 && arr[j]-arr[i]+1 <= 2*w) {
			//cerr << "Entro aca" << endl;
			// si tenemos q
			if (qres) qres--;
			// si solo tenemos p
			else if (pres >= 2) pres-=2;
			// si no tenemos suficientes p ni q
			else {
				//cerr << "FAIL" << endl;
				return false;
			}
		}
		// si debemos usar una p
		else if (pres) pres--;
		// no tenemos suficiente, así que usamos q
		else if (qres) qres--;
		// no se puede, no hay tortillas
		else {
			//cerr << "FAIL" << endl;
			return false;
		}
		
		i = j+1;
	}
	
	//cerr << "OK" << endl;
	return true;
}

int main() {
	/*//
	freopen("watching.in", "r", stdin);
	freopen("", "w", stdout);
	//*/
	
	cin >> n >> p >> q;
	arr.resize(n);
	for (int i=0; i<n; i++) cin >> arr[i];
	
	sort(arr.begin(), arr.end());
	
	/*//
	cerr << "A: [";
	for (int x : arr) cerr << x << ", ";
	cerr << "]" << endl;
	//*/
	
	ll lb = 1, ub = 1e9, mid;
	while (lb <= ub) {
		mid = (lb+ub)/2;
		if (Check(mid)) ub = mid-1;
		else lb = mid+1;
	}
	
	cout << ub+1 << endl;
	return 0;
}

Subtask #1
0 / 50.0

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

Subtask #2
0 / 50.0

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