This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2005;
int n , p , q , ans = 1e9;
int a[N] , cnt[N];
bool check(int mid){
int x = p , y = q;
bool ok = false;
for(int i = 1 ; i <= n &&(p > 0 || q > 0); ++ i){
int cur1 = i , idem1 = 0;
for(; cur1 <= n ; ++ cur1){
if(a[cur1] - a[i] >= mid ) break;
idem1 ++;
}
int cur2 = i , idem2 = 0;
for(; cur2 <= n ; ++ cur2){
if(a[cur2] - a[i] >= 2*mid ) break;
idem2 ++;
}
if(p == 0) q-- , i = cur2 - 1;
else if(q == 0) p-- , i = cur1 - 1;
else if(idem2 >= idem1 * 2) q-- , i = cur2 - 1;
else p-- , i = cur1 - 1;
if(i == n) ok =true;
}
p = x ; q =y;
return ok;
}
signed main(){
//freopen("1.inp","r",stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> p >> q;
a[n+1] = 1e9;
for(int i = 1 ;i <= n ; ++ i )
cin >> a[i];
sort(a + 1 , a + n + 1);
if( p+q >= n ){
cout << 1;
return 0;
}
int l = 1 , r = a[n] - a[1] + 1;
while(l <= r){
int mid = ( l+ r ) / 2;
bool kt = check(mid);
if(kt){
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |