Pagini recente » Cod sursa (job #2599842) | Cod sursa (job #2618900) | Cod sursa (job #2360207) | Cod sursa (job #1526716) | Cod sursa (job #509490)
Cod sursa(job #509490)
# include <fstream>
# include <iostream>
# include <cstdio>
# define DIM 30003
using namespace std;
int n, l, u, c[DIM], t[DIM], v[DIM], dq[DIM], sol;
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]+c[i]-K*t[i];
int st=1, dr=1, smax=-2000000000;
dq[1]=0;
for(int i=l;i<=n;++i)
{
if (v[i]-v[dq[st]]>smax)
smax=v[i]-v[dq[st]];
while (v[i]<=v[dq[dr]] && dr>=st)--dr;
dq[++dr]=i;
if (i-dq[st]==u)
++st;
}
return smax;
}
void cauta (int st, int dr)
{
if (st==dr)
{
if (sol<st && f(st)>0)
sol=st;
return;
}
int mij=(st+dr)/2;
if (f(mij)<0)
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;
}