Cod sursa(job #66124)

Utilizator crawlerPuni Andrei Paul crawler Data 15 iunie 2007 21:30:37
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <cstdio>

using namespace std;

#define Nmax 30100

int c[Nmax], t[Nmax],n,L,U, dq[Nmax];
double a[Nmax];

double rez(double X)
{
	for (int i=1;i<=n;++i)
		a[i] = (double)(a[i-1] + c[i] - t[i]*X);
	double max=-1234567890;
	int st=1,dr=1;
	dq[st] = 0;
	for (int i=L;i<=n;++i)
	{
		if(max < a[i] - a[dq[st]])
			 max = a[i] - a[dq[st]];		
		while(a[dq[dr]] >= a[i-L+1] && st<=dr) --dr;
		dq[++dr] = i-L+1;
		if(dq[st] == i-U) ++st;
	}		
	return max;
}	

int main()
{
	freopen("secv3.in","r",stdin);
	freopen("secv3.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]);

	double st=0.0001, dr=1000, tmp;

	while(dr-st > 0.000001)
	{
		double mij = (st+dr)/2;
		tmp = rez(mij);
		if(tmp == 0) 
		 st = dr = mij;		

		if(tmp < 0)
			dr = mij;
			 else
			st = mij;
	}

	printf("%.2f\n",dr);

	return 0; 
}