Cod sursa(job #66120)
#include <cstdio>
using namespace std;
#define Nmax 30100
int c[Nmax], t[Nmax],n,L,U, dq[Nmax];
double a[Nmax];
double rez(double X)
{
for (int i=1;i<=n;++i)
a[i] = (double)(a[i-1] + c[i] - t[i]*X);
double max=a[1];
int st=1,dr=1;
dq[st] = 0;
for (int i=L;i<=n;++i)
{
if(max < a[i] - a[dq[st]])
max = a[i] - a[dq[st]];
while(a[dq[dr]] >= a[i-L] && st<dr) --dr;
dq[++dr] = i;
if(dq[st] == i-U) ++st;
}
return max;
}
int main()
{
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
scanf("%d%d%d",&n,&L,&U);
for (int i=1;i<=n;++i)
scanf("%d",&c[i]);
for (int i=1;i<=n;++i)
scanf("%d",&t[i]);
double st=0.0001, dr=1000, tmp;
while(dr-st > 0.0001)
{
double mij = (st+dr)/2;
tmp = rez(mij);
if(tmp == 0)
{
st = mij;
break;
}
if(tmp < 0)
dr = mij;
else
st = mij;
}
printf("%.2f\n",st);
return 0;
}