Cod sursa(job #379689)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 3 ianuarie 2010 13:15:20
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>
#include <string.h>
#define NMAX 30001
#define LIM 0.001
int n,l,u,A[NMAX],B[NMAX],inc,sf,deq[NMAX];
double val=(1<<15),C[NMAX],sum[NMAX],rez;
void read()
{
	scanf("%d%d%d",&n,&l,&u);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d",&A[i]);
	for (i=1; i<=n; i++)
		scanf("%d",&B[i]);
}
void capat(int i)
{
	if (i-deq[inc]>l+1)
		inc++;
}
void actualizare(int i)
{
	while (inc!=sf && sum[i]<=sum[deq[sf-1]])
		--sf;
	deq[sf++]=i;
}
inline int ok(double x)
{
	int i;
	inc=0;sf=0;
	for (i=1; i<=n; i++)
		C[i]=(double)A[i]-(double)B[i]*x;
	memset(deq,0,sizeof(deq));
	for (i=1; i<=n; i++)
	{
		sum[i]=sum[i-1]+C[i];
		if (i>=l && sum[i]-sum[deq[inc]]>=0)
			return 1;
		if (i>=l)
		{
			actualizare(i-l+1);
			capat(i-l+1);
		}
	}
	return 0;
}
void cbin()
{
	while (val>LIM)
	{
		if (ok(rez+val))
			rez+=val;
		val/=2;
	}
}
int main()
{
	freopen("secv3.in","r",stdin);
	freopen("secv3.out","w",stdout);
	read();
	cbin();
	printf("%.2lf\n",rez);
	return 0;
}