#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c;
int z[1000005];
vector <int> v;
vector <int> v1;
bool check(int mid){
int sta=z[1];
int cnt=0;
while (true){
cnt++;
int pos= upper_bound(z+1,z+1+a,sta+mid-1)-z-1;
if (pos==a){
break;
}
sta=z[pos+1];
}
return cnt<=b+c;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b >> c;
for (int i=1;i<=a;i++){
cin >> z[i];
}
sort(z+1,z+1+a);
if (b+c>a){
cout << 1 << "\n";
return 0;
}
int l=1;
int r=1e9+7;
int pos=1e9+7;
while (l<=r){
int mid=(l+r)/2;
if (check(mid)){
pos=mid;
r=mid-1;
}else{
l=mid+1;
}
}
int sta=z[1];
while (true){
int pos1= upper_bound(z+1,z+1+a,sta+pos-1)-z-1;
v.push_back(z[pos1]-sta+1);
// cout << pos1 << " ";
// cout << z[pos1]-z[sta] << " ";
if (pos1==a){
break;
}
sta=z[pos1+1];
}
sort(v.begin(),v.end());
for (int i=1;i<=c;i++){
int p= v.back()/2 + (v.back()%2);
// cout << p << " ";
v1.push_back(p);
v.pop_back();
}
for (int i=0;i<c;i++){
v.push_back(v1[i]);
}
sort(v.begin(),v.end());
cout << v.back() << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |