Cod sursa(job #461629)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 8 iunie 2010 00:00:56
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>

#define file_in "secv3.in"
#define file_out "secv3.out"

#define nmax 30100

int n,L,U;
int c[nmax];
int t[nmax];
double sol;


void citire()
{
	freopen(file_in,"r",stdin);
	freopen(file_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]);
}

int ok(double X)
{
	
	double q[nmax];
	double a[nmax];
	int i;
	
	q[0]=0;
	for (i=1;i<=n;++i)
		 q[i]=q[i-1]+(double)c[i]-(double)(X*t[i]);
	
	int p,u;
	int d[nmax];
		 
	p=1;
	u=0;
	
    for (i=1;i<=n;++i)
	{
		while(p<=u && q[d[u]]>=q[i]) u--;
		d[++u]=i;
		while(p<=u && i-d[p]>U-L) p++;
		a[i]=q[i]-q[d[p]];
	}
	
	for (i=1;i<=n;++i)
	     if (q[i]-q[i-L]+a[i-L]>=0) 
	          return 1;
	return 0;
}	
	

void solve()
{
	double ls,ld,mij;
	
	ls=0;
	ld=1000*100+5;
	
	while(ls<=ld)
	{
		mij=(ls+ld)/2;
		
		if (ok(mij))
		{
			sol=mij;
			ls=mij+0.001;
		}
		else
			ld=mij-0.001;
	}
	
	printf("%lf\n", sol);
}

int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}