Cod sursa(job #384189)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 19 ianuarie 2010 16:41:48
Problema Secventa 3 Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.51 kb
#include<stdio.h>
#define infile "secv3.in"
#define outfile "secv3.out"
#define nmax 31313
#define vmax 1000
int a[nmax]; //secventa cu costurile
int b[nmax]; //secventa cu timpii
int n; //lungimea secventelor
int l,u; //lungimea minima, respectiv lungimea maxima a subsecventelor
double med; //media maxima

void read()
{
	int i;
	scanf("%d %d %d\n",&n,&l,&u);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	for(i=1;i<=n;i++) scanf("%d",&b[i]);
}

int verif(double med)
{ //trebuie sa verificam daca se poate obtine aceasta medie
	double c[n+1]; //c[i]=a[1]-med*b[1] + a[i]-med*b[i]
	double d[n+1]; //d[i]=suma unei subsecvente de lungime cel mult (u-l+2) din c[] ce se termina pe pozitia i
	int e[n+1],st,dr; //deq
	int i;
	
	//il construim pe c
	for(c[0]=0,i=1;i<=n;i++)
		c[i]=c[i-1]+(double)a[i]-(med*b[i]);
	
	
	
	//facem deq-ul
	for(st=1,dr=0,i=1;i<=n;i++)
	{
		while(st<=dr && c[e[dr]]>=c[i]) dr--;
		e[++dr]=i;
		while(st<=dr && i-e[st] > u-l) st++;
		d[i]=c[i]-c[e[st]];
	}
	
	//acum trebuie sa verificam daca exista o secventa cu suma pozitiva
	for(i=l;i<=n;i++)
		if(c[i]-c[i-l]+d[i-l] >= 0)
			return 1;
	
	//daca am ajuns aici, inseamna ca toate subsecventele sun negative
	return 0;
}

void solve()
{
	double mij,st=0,dr=vmax;
	while(st<=dr)
	{ //cautam binar media
		mij=(st+dr)/2;
		if(verif(mij)) med=mij,st=mij+0.000001;
		else dr=mij-0.000001;
	}
}

void write()
{
	printf("%lf\n",med);
}

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	
	read();
	solve();
	write();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}