#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
int n,a,b,all[maxn],dp[maxn][maxn];
void vorod(){
cin>>n>>a>>b;
a=min(n,a);
b=min(n,b);
for(int i=1;i<=n;i++){
cin>>all[i];
}
sort(all+1,all+n+1);
}
int check(int len){
for(int i=1;i<=n;i++){
int l1=0,l2=0;
while(l1+1<i&&all[i]-all[l1+1]+1>len*2){
l1++;
}
while(l2+1<i&&all[i]-all[l2+1]+1>len){
l2++;
}
for(int j=0;j<=a;j++){
dp[i][j]=dp[l1][j]+1;
if(j>0){
dp[i][j]=min(dp[i][j],dp[l2][j-1]);
}
//cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
}
}
return dp[n][a]<=b;
}
void solve(){
int low=-1,high=2e9+1,mid;
while(high-low>1){
mid=(high+low)>>1;
if(check(mid)){
high=mid;
}else{
low=mid;
}
}
cout<<high<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("inp.txt","r",stdin);
vorod();
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
15500 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
