제출 #1123047

#제출 시각아이디문제언어결과실행 시간메모리
1123047nuutsnoynton구경하기 (JOI13_watching)C++20
0 / 100
1094 ms584 KiB
#include<bits/stdc++.h>

using namespace std;
using ll = long long ;
ll a[2005], n, small, big, sz_small, sz_big;
bool Can(ll ind, ll s_cnt, ll b_cnt) {
	if ( ind == n + 1) return true;
	if ( s_cnt == 0 && b_cnt == 0) return false;
	if ( s_cnt == 0) return Can(upper_bound(a + 1, a + n + 1, a[ind] + sz_big - 1) - a, s_cnt, b_cnt-1);
	if ( b_cnt == 0) return Can(upper_bound(a + 1, a + n + 1, a[ind] + sz_small - 1) - a, s_cnt- 1, b_cnt);
	return Can(upper_bound(a + 1, a + n + 1, a[ind] + sz_small - 1) - a, s_cnt- 1, b_cnt) || Can(upper_bound(a + 1, a + n + 1, a[ind] + sz_big - 1) - a, s_cnt, b_cnt-1);
}
bool Solve(ll x) {
	sz_small = x;
	sz_big = 2 * x;
	return Can(1, small , big);
}
int main() {
//	freopen("moocast.in", "r", stdin);
//	freopen("moocast.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll t, m, ans, s, lo, hi, sum, x, y, r, p, i, j, mid;

	cin >> n >> small >> big;
	
	for (i = 1; i <= n; i ++) cin >> a[i];
	sort ( a + 1, a + n + 1);
	lo = 1;
	hi = 1e9;
	while ( lo < hi) {
		mid =(lo + hi)/2;
		if (!Solve(mid)) lo = mid + 1;
		else hi = mid;
	}
	cout << lo << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...