Pagini recente » Cod sursa (job #1404503) | Cod sursa (job #1148561) | Cod sursa (job #2929476) | Cod sursa (job #273154) | Cod sursa (job #198473)
Cod sursa(job #198473)
#include <stdio.h>
using namespace std;
#define NMAX 30002
#define INF 0x3f3f3f3f
#define eps 1e-4
double D[NMAX][2];
double X[NMAX],Y[NMAX];
long int l,u,n;
int verif(double k)
{
double a[NMAX];
long int i,st,dr,x;
a[0]=0;
for (i=1;i<=n;i++)
a[i]=a[i-1]+X[i]-k*Y[i];
st=1;
dr=0;
// printf("XXXXXXXXXXXXX\n%.2lf\n",k);
// for (i=1;i<=n;i++) printf("%.2lf ",a[i]);
// printf("\n");
for (i=l;i<=n;i++)
{
x=i-l+1;
for (;(D[dr][0]>a[x])&&(dr>=st);dr--);
D[++dr][0]=a[x];
D[dr][1]=x;
for (;(D[st][1]<=i-u)&&(st<=dr);st++);
// printf("%.2ld %2.lf ",a[i],D[st][0]);
if ( a[i]-D[st][0] > -eps ) return 1;
}
return 0;
}
int main()
{
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
long int i,j;
double st,dr,mid;
scanf("%ld %ld %ld",&n,&l,&u);
l++;u++;
for (i=1;i<=n;i++)
scanf("%lf",&X[i]);
for (i=1;i<=n;i++)
scanf("%lf",&Y[i]);
st=0;
dr=INF;
while (dr-st>eps)
{
mid=(st+dr)/2;
if ( verif(mid) )
st=mid;
else dr=mid;
}
printf("%.3lf",st);
return 0;
}