oj.uz

답안 #51453

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51453 2018-06-18T03:06:48 Z huynhsmd 구경하기 (JOI13_watching) C++17
0 / 100
 3 ms 620 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
const int N = 4005;

int  n , p , q , ans = 1e10;
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) 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 548 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Incorrect 2 ms 560 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 560 KB Output is correct
2 Correct 3 ms 560 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 3 ms 560 KB Output is correct
5 Correct 3 ms 560 KB Output is correct
6 Correct 2 ms 608 KB Output is correct
7 Incorrect 2 ms 620 KB Output isn't correct
8 Halted 0 ms 0 KB -