Cod sursa(job #246384)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 20 ianuarie 2009 19:48:35
Problema Secventa 3 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <cstdio>
#define x 100
#define lm 30001

long t[lm],c[lm],n,i,r,l,u;
long long v[lm],s[lm];

bool smax(long k)
{
	long i,d,j,a[lm],p[lm],st,dr;
	long long q[lm],sm,b;
	d=u-l+1;
	for (i=1; i<=n; i++) a[i]=c[i]-(k*t[i]);
	for (i=1; i<=n; i++) s[i]=s[i-1]+a[i];
	st=1;
	dr=1;
	q[1]=a[1];
	p[1]=1;
	v[1]=a[1];
	for (i=2; i<=n; i++)
	{
		while (p[st]+d<i) st++;
		v[i]=s[i]-q[st];
		while ((s[i]<=q[dr])&(dr>=st)) dr--;
		dr++;
		q[dr]=s[i];
		p[dr]=i;
    }
	sm=-1;
	for (i=l; i<=n; i++)
	{
	    b=0;
		b=s[i]-s[i-l+1];
		b+=v[i-l+1];
		if (b>sm) sm=b;
    }
	if (sm>-1) sm=1; else sm=0;
	return sm;
}


long caut(long a, long b)
{
	long k,r;
    while (a<=b)
    {
	    k=(a+b)/2;
		if (smax(k))
		{
			r=k;
			a=k+1;
        } else b=k-1;
	}
	return r;
}
	
int main()
{
    freopen("secv3.in","r",stdin);
	freopen("secv3.out","w",stdout);
	scanf("%ld %ld %ld",&n,&l,&u);
	for (i=1; i<=n; i++)
	{
	    scanf("%ld",&c[i]);
		c[i]*=x;
	}
	for (i=1; i<=n; i++) scanf("%ld",&t[i]);
	r=caut(1,30000000);
	printf("%ld.",r/x);
	if (r%x<10) printf("0");
	printf("%ld\n",r%x);
//	smax(50);
}