#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) {
bool dp[2002][2002][2002] = {0};
int i, j,r;
dp[n][small][large]= 1;
for (i = n; i >= 1; i --) {
for (j = 0; j <= small; j ++) {
for ( r = 0; r <= large; r ++) {
if ( r > 0 && dp[i][j][r]) {
s = lower_bound(a + 1, a + n + 1, a[i] - (2 * x) + 1) - a;
s --;
if (s == 0) return true;
dp[s][j][r - 1] = 1;
}
if ( j > 0 && dp[i][j][r]) {
s = lower_bound(a + 1, a + n + 1, a[i] - x + 1) - a;
s --;
if (s == 0) return true;
dp[s][j - 1][r] = 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, j;
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;
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:38:35: warning: unused variable 'j' [-Wunused-variable]
38 | ll i, lo, hi, mid, small, large, j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
150 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
127 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
