oj.uz

Submission #981229

# Submission time Handle Problem Language Result Execution time Memory
981229 2024-05-13T02:36:58 Z Amaarsaa Watching (JOI13_watching) C++14
0 / 100
 1000 ms 604 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long ;
ll a[2004];
ll n;
bool Can(ll x, ll s, ll small, ll large) {
	ll p;
	if ( s < 1) return 1;
	if ( small > 0) {
		p = lower_bound(a + 1, a + n + 1, a[s] - x + 1) - a;
		p --;
		if (Can(x, p, small- 1, large)) return 1;
	} 
	if ( large > 0) {
		p = lower_bound(a + 1, a + n + 1, a[s] - (2 * x) + 1) - a;
		p --;
		if (Can(x, p, small, large - 1)) return 1;	
	}
	return 0;
}

int main() {
//	freopen("moocast.in", "r", stdin);
//	freopen("moocast.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll i, lo, hi, mid, small, large;
	
	cin >> n >> small >> large;
	if ( small + large >= n) {
		cout << 1 << endl;
		return 0;
	}
	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 ( !Can(mid, n, small, large)) lo = mid + 1;
		else hi = mid;
	}
	cout << lo  << endl;
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 7 ms 604 KB Output is correct
10 Execution timed out 1037 ms 348 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Execution timed out 1071 ms 348 KB Time limit exceeded
8 Halted 0 ms 0 KB -