Cod sursa(job #66353)

Utilizator peanutzAndrei Homorodean peanutz Data 17 iunie 2007 20:57:28
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <stdio.h>
#include <math.h>
#define eps 0.01

#define NMAX 30004

double s[NMAX];
int n, l, u;
double max;

void read()
{
	int i;
	double t[NMAX];
	t[0] = 0;
	scanf("%d %d %d", &n, &l, &u);
	for(i = 1; i <= n; ++i)
		scanf("%lf", s+i);
	for(i = 1; i <= n; ++i)
		scanf("%lf", t+i), s[i] = s[i-1] + s[i]/t[i];
}

int ok(double m)
{
	int st = 1, dr = l;
	double max = 0;

	while(dr <= n)
	{

		if(max-s[dr]+s[st-1] >= eps)
			max = s[dr]-s[st-1];

		if(m-s[dr]+s[st-1] > eps)
			++dr;
		else if(s[dr]-s[st-1]-m > eps)
			++st;

		if(dr-st+1 <= l)
		       ++dr;
		else if(dr-st+1 >= u)
			++st;

		if(dr > n)
			return 0;

		if(m-s[dr]+s[st-1] <= eps)
			return 1;

		if(s[dr]-s[st-1]-max > eps)
			max = s[dr]-s[st-1];

	}
	if(max-m >= eps)
		return 2;
	return 0;
}

void binary_search()
{
	double st, dr, m, eps2 = eps;// * 0.1;
	int aux;

	st = 0;
	dr = NMAX*2000;

	while(dr-st >= eps2)
	{
		m = (dr + st)/2;
		aux = ok(m);

		if(aux == 1)
		{
			max = m;
			st = m + eps;
		}
		else if(aux == 2)
		{
			st = m + eps;
		}
		else if(aux == 0)
		{

			dr = m - eps;
		}
	}
}
int main()
{
	freopen("secv3.in", "r", stdin);
	freopen("secv3.out", "w", stdout);

	read();

	binary_search();

	//max = floor(max*100)/100;
 	printf("%.2lf\n", max);

	fclose(stdin);
	fclose(stdout);

	return 0;
}