oj.uz

Submission #51449

# Submission time Handle Problem Language Result Execution time Memory
51449 2018-06-18T02:57:58 Z huynhsmd Watching (JOI13_watching) C++17
0 / 100
 3 ms 564 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
const int N = 2005;
int  n , p , q , ans = 1e9;
int a[N] , cnt[N];

bool check(int mid){
	int x = p , y = q; 
	bool ok = false;
	for(int i = 1 ; i <= n &&(p > 0 || q > 0); ++ i){
		int cur1 = i , idem1 = 0;
		for(; cur1 <= n ; ++ cur1){
			if(a[cur1] - a[i] >= mid ) break;
			idem1 ++;
		}
		int cur2 = i , idem2 = 0;
		for(; cur2 <= n ; ++ cur2){
			if(a[cur2] - a[i] >= 2*mid ) break;
			idem2 ++;
		}		
		if(p == 0) q-- , i = cur2 - 1;
		else if(q == 0) p-- , i = cur1 - 1;
		else if(idem2 >= idem1 * 2) q-- , i = cur2 - 1;
		else p-- , i = cur1 - 1;
		if(i == n) ok =true;
	}
	p = x ; q =y;
	return ok;
}
signed main(){
	//freopen("1.inp","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> p >> q;
	a[n+1] = 1e9;
	for(int i = 1 ;i <= n ; ++ i )
		cin >> a[i];
	sort(a + 1 , a + n + 1);	
	if( p+q >= n ){
		cout << 1;
		return 0;
	}
	int l = 1 , r = a[n] - a[1] + 1;
	while(l <= r){
		int mid = ( l+ r ) / 2;
		bool kt = check(mid);
		if(kt){
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	
	cout << ans;
}

Subtask #1
0 / 50.0

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

Subtask #2
0 / 50.0

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