Pagini recente » Cod sursa (job #677564) | Istoria paginii utilizator/gheorghe_alexandru_stefan_323ca | Monitorul de evaluare | Istoria paginii utilizator/horiatomescu | Cod sursa (job #509544)
Cod sursa(job #509544)
# 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=v[l];
dq[1]=0;
for(int i=l;i<=n;++i)
{
while (v[i-l]<=v[dq[dr]] && dr>=st)--dr;
dq[++dr]=i-l;
if (v[i]-v[dq[st]]>smax)
smax=v[i]-v[dq[st]];
while (i-dq[st]>=u)
++st;
}
if (smax>0)
return 1;
return 0;
}
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
{
sol=mij;
cauta(mij+1, dr);
}
}
int main ()
{
read ();
cauta (0, 100001);
freopen("secv3.out", "w", stdout);
printf("%.2lf", sol/100.);
return 0;
}