Cod sursa(job #198473)

Utilizator devilkindSavin Tiberiu devilkind Data 11 iulie 2008 18:09:44
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#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;
}