Pagini recente » Cod sursa (job #2358901) | Cod sursa (job #2977063) | Cod sursa (job #2505892) | Cod sursa (job #611108) | Cod sursa (job #509501)
Cod sursa(job #509501)
# include <fstream>
# include <iostream>
# include <cstdio>
# define DIM 30003
using namespace std;
int n, l, u, c[DIM], t[DIM], dq[DIM], sol;
long long v[DIM];
void read ()
{
ifstream fin ("secv3.in");
fin>>n>>l>>u;
for(int i=1;i<=n;++i)
fin>>c[i], c[i]*=100;
for(int i=1;i<=n;++i)
fin>>t[i];
}
int f (int K)
{
for (int i=1;i<=n;++i)
v[i]=v[i-1]+(long long)c[i]-K*t[i];
int st=1, dr=1;
long long smax=-2000000000;
dq[1]=0;
for(int i=l;i<=n;++i)
{
if (v[i]-v[dq[st]]>smax && i-dq[st]>=l)
smax=v[i]-v[dq[st]];
while (v[i]<=v[dq[dr]] && dr>=st)--dr;
dq[++dr]=i;
if (i-dq[st]>=u)
++st;
}
if (smax<0)
return 0;
return 1;
}
void cauta (int st, int dr)
{
if (st==dr)
{
if (sol<st && f(st))
sol=st;
return;
}
int mij=(st+dr)/2;
if (!f(mij))
cauta(st, mij);
else
{
if (mij>sol)sol=mij;
cauta(mij+1, dr);
}
}
int main ()
{
read ();
cauta (0, 100001);
freopen("secv3.out", "w", stdout);
printf("%.2lf", sol/100.);
return 0;
}