#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
int a[3010];
int mn[12000];
struct st
{
int ex,one,two;
bool operator <(const st&o) const
{
if(ex+one+two==o.ex+o.one+o.two)
return two>o.two;
return ex+one+two<o.ex+o.one+o.two;
}
};
void build(int l,int r,int i)
{
if(l==r)
{
mn[i]=a[l];
return;
}
int mid=(l+r)/2;
build(l,mid,i*2);
build(mid+1,r,i*2+1);
mn[i]=min(mn[i*2],mn[i*2+1]);
}
int query(int l,int r,int i,int val)
{
if(l==r)
return l;
int mid=(l+r)/2;
if(mn[i*2+1]<=val)
return query(mid+1,r,i*2+1,val);
else
return query(l,mid,i*2,val);
}
signed main()
{
int n,p,q;
cin>>n>>p>>q;
for(int i=1;i<=n;i++)
cin>>a[i];
a[0]=0;
sort(a+1,a+n+1);
build(0,n,1);
int l=1,r=1e9;
while(l<r)
{
int mid=(l+r)/2;
st dp[n+1];
for(int i=0;i<=n;i++)
dp[i]={0,0,0};
for(int i=1;i<=n;i++)
{
int index1=query(0,n,1,max((int)0,a[i]-mid));
int index2=query(0,n,1,max((int)0,a[i]-mid*2));
st p1=dp[index1],p2=dp[index2];
/*if(p1.ex==1)
{
p1.ex=0;
p1.two+=2;
}
else
p1.ex++;*/
p1.one++;
p2.two+=2;
if(p1<p2)
dp[i]=p1;
else
dp[i]=p2;
/*cout<<a[i]-mid<<" "<<a[i]-mid*2<<endl;
cout<<index1<<' '<<index2<<endl;
cout<<p1.ex<<" "<<p1.one<<" "<<p1.two<<'\n';
cout<<p2.ex<<" "<<p2.one<<" "<<p2.two<<'\n';
cout<<dp[i].ex<<" "<<dp[i].one<<" "<<dp[i].two<<'\n';
cout<<endl;*/
}
int ex=dp[n].ex,one=dp[n].one,two=dp[n].two;
int pp=p,qq=q;
two/=2;
if(two<=qq)
{
qq-=two;
two=0;
}
else
{
two-=qq;
qq=0;
two*=2;
}
if(two+one+ex<=qq+pp)
r=mid;
else
l=mid+1;
}
cout<<l;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |