#include<bits/stdc++.h>
using namespace std;
using ll = int;
ll a[2003], big, small, n;
bool Can(ll x) {
ll i, j, r, s;
vector < vector < ll > > dp(big + 1, vector < ll > (small + 1));
dp[big][small] = 0;
for (i = big; i >= 0; i --) {
for (j = small; j >= 0; j --) {
if( dp[i][j] == n) return 1;
r = dp[i][j];
if ( i > 0) {
s = a[r + 1] + 2 * x ;
s = lower_bound(a + 1, a + n + 1, s) - a - 1;
dp[i - 1][j] = max(dp[i - 1][j], s);
}
if ( j > 0) {
s = a[r + 1] + x ;
s = lower_bound(a + 1, a + n + 1, s) - a - 1;
dp[i][j - 1] = max ( dp[i][j - 1], s);
}
}
}
return 0;
}
int main() {
ll m, r, x, y, i, j, lo, hi, mid, ans, t;
cin >> n >> small >> big;
small = min(n, small);
big = min(n, big);
for (i = 1; i <= n; i++) {
scanf("%d",& a[i]);
}
sort ( a + 1, a + n + 1);
lo = 0;
hi = 1e9;
while ( lo < hi) {
mid = (lo + hi)/2;
if ( !Can(mid)) lo = mid + 1;
else hi = mid;
}
cout << lo << endl;
}
Compilation message (stderr)
watching.cpp: In function 'int main()':
watching.cpp:38:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | scanf("%d",& a[i]);
| ~~~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |