Submission #1123047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123047		nuutsnoynton	Watching (JOI13_watching)	C++20	0 / 100	1094 ms	584 KiB

watching

#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;
}

• Subtask 1: 0 / 50
• Subtask 2: 0 / 50