Cod sursa(job #458098)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 23 mai 2010 09:38:09
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <cstdio>

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

#define nmax 30100

int n,l,U;
double c[nmax];
double t[nmax];
double suma[nmax];
double b[nmax];
int d[nmax];

void citire()
{
	int i;
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d %d", &n,&l,&U);
	for (i=1;i<=n;++i)
		 scanf("%lf", &c[i]);
	for (i=1;i<=n;++i)
		 scanf("%lf", &t[i]);
}

double secv(double X)
{
   
	int i,sol;
	
	for (i=1;i<=n;++i)
		 b[i]=c[i]-t[i]*X;
	
	suma[0]=0;
	//calculeaza suma pana la l
	for (i=1;i<=l;++i) suma[0]+=b[i];
	int p,u;
	p=0;
	u=0;
	double q=0,max=suma[0];
	double x=suma[0];
	d[p]=1;
	for (i=l+1;i<=n;++i)
	{
		q+=b[i];
		x-=b[i-l];
		while(p<=u && i-d[p]>=U) p++;
		while(p<=u && suma[u]<x) u--;
		suma[++u]=x;
		d[u]=i-l+1;
		if (p<=u && suma[p]+q>max)
			max=q+suma[p];
	}
	
	return max;
}

double abs(double x) { return x>=0?x:-x; }

void solve()
{
	double ls,ld;
	double mij;
	double sol=0.0;
	ls=0;
	ld=10000;
	
	while(ls<=ld)
	{
		mij=(double)((ls+ld)/2);
		double x=(secv(mij));
		if (x-sol>0.01)
		{
			sol=x;
			ls=mij+1;
		}
		else
			ld=mij-1;
	}

	
	printf("%.2lf\n", sol);
}

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