#include <bits/stdc++.h>
using namespace std;
int a[2005];
int n,p,q;
int dp[2005][2005];
int check(int w){
for(int i=0; i<=p; i++){
for(int j=0; j<=q; j++){
int pos,opos;
if(i!=p){
pos=opos=dp[i][j]+1;
while(pos<n-1){
if(a[pos+1]-a[opos]<w) pos++;
else break;
}
dp[i+1][j]=max(dp[i+1][j],min(pos,n-1));
}
if(j!=q){
pos=opos=dp[i][j]+1;
while(pos<n-1){
if(a[pos+1]-a[opos]<w*2) pos++;
else break;
}
dp[i][j+1]=max(dp[i][j+1],min(pos,n-1));
}
}
}
}
int bs(){
int l=1,r=10,mid;
while(l<=r){
for(int i=0; i<=p; i++){
for(int j=0; j<=q; j++){
dp[i][j]=0;
}
}
dp[0][0]=-1;
mid=(l+r)/2;
check(mid);
if(dp[p][q]==n-1) r=mid-1;
else l=mid+1;
}
return l;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>p>>q;
for(int i=0; i<n; i++) cin>>a[i];
sort(a,a+n);
if(p+q>=n){
cout<<1;
return 0;
}
cout<<bs();
return 0;
}
Compilation message (stderr)
watching.cpp: In function 'int check(int)':
watching.cpp:31:1: warning: no return statement in function returning non-void [-Wreturn-type]
31 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |