Pagini recente » Cod sursa (job #3160654) | Cod sursa (job #1740484) | Cod sursa (job #2977037) | Cod sursa (job #2134224) | Cod sursa (job #509498)
Cod sursa(job #509498)
# 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, 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;
}
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;
}