#include<bits/stdc++.h>
using namespace std;
const int MAXN=2024;
long long pos[MAXN];
int dp[MAXN][MAXN],nex[MAXN][2];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,p,q;
cin>>n>>p>>q;
p=min(p,n),q=min(q,n);
for(int i=1;i<=n;i++) cin>>pos[i];
sort(pos+1,pos+n+1);
long long l=1,r=1e9,ans=0;
while(l<=r)
{
long long mid=(l+r)/2;
for(int i=1;i<=n;i++)
{
nex[i][0]=upper_bound(pos+1,pos+n+1,pos[i]+mid-1)-pos-1;
nex[i][1]=upper_bound(pos+1,pos+n+1,pos[i]+mid*2-1)-pos-1;
}
nex[n+1][0]=nex[n+1][1]=n;
for(int i=0;i<=p;i++) for(int j=0;j<=q;j++) if(i==0&&j==0) dp[i][j]=0;
else
{
dp[i][j]=0;
if(i>0) dp[i][j]=max(dp[i][j],nex[dp[i-1][j]+1][0]);
if(j>0) dp[i][j]=max(dp[i][j],nex[dp[i][j-1]+1][1]);
}
if(dp[p][q]==n) r=mid-1,ans=mid;
else l=mid+1;
}
cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |