Pagini recente » Cod sursa (job #3141097) | Cod sursa (job #57315) | Cod sursa (job #3201300) | Cod sursa (job #519481) | Cod sursa (job #3153902)
#include <fstream>
using namespace std;
ifstream cin("secv3.in");
ofstream cout("secv3.out");
long double sp1[30001],sp2[30001];
struct ura
{
int ind;
long double rez;
}dq[30001];
int main()
{
int n,l,u,i,j1,j2,ok;
long double st=0,dr=1e3,mij,poz,sum;
cin>>n>>l>>u;
for(i=1;i<=n;i++)
{
cin>>sp1[i];
sp1[i]+=sp1[i-1];
}
for(i=1;i<=n;i++)
{
cin>>sp2[i];
sp2[i]+=sp2[i-1];
}
while(st<=dr)
{
mij=(st+dr)/2;
ok=0;
dq[1].ind=0;
dq[1].rez=0;
for(j1=1,j2=1,i=l;i<=n&&ok==0;i++)
{
if(dq[j1].ind<i-u)
j1++;
sum=sp1[i-l]-sp2[i-l]*mij;
while(j2>=j1&&dq[j2].rez>=sum)
j2--;
j2++;
dq[j2].rez=sum;
dq[j2].ind=i-l;
if(sp1[i]-sp2[i]*mij-dq[j1].rez>=0)
ok=1;
}
if(ok==0)
dr=mij-0.001;
else
{
poz=mij;
st=mij+0.001;
}
}
cout<<poz;
return 0;
}