Cod sursa(job #2552219)

Utilizator dariusandreicotaeCotae Darius Andrei dariusandreicotae Data 20 februarie 2020 17:59:54
Problema Secventa 3 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<stdio.h>
#define nmax 30000
int u,l,i,j,n,a[nmax],b[nmax],poz[nmax];
double dek[nmax],c[nmax];
int main()
{
	freopen("secv3.in","r",stdin);
	freopen("secv3.out","w",stdout);

	scanf("%d %d %d",&n,&l,&u);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(i=1;i<=n;i++)
		scanf("%d",&b[i]);
	double k,in=0,sf=1000;
	while(sf-in>=0.001)
	{
		k=(in+sf)/2;
		for(i=1;i<=n;i++)
		{
			c[i]=c[i-1]+a[i]-b[i]*k;
		}
		int p=0,q=-1;
		double sum=-nmax;
		for(i=1;i<=n;i++)
		{
			while(p<=q&& poz[p]<i-u)
				p++;
			if(i-l>=0)
			{
				while( p<=q && c[i-l]<dek[q])
					q--;
				q++;

				dek[q]=c[i-l];
				poz[q]=i-l;
				if(c[i]-dek[p]>sum)
				{
					sum=c[i]-dek[p];
				}
			}
		}
		if(sum>0)
			in=k;
		else
			sf=k;
	}

	printf("%0.2lf",sf);
	return 0;

}