Cod sursa(job #27735)

Utilizator pocaituDavid si Goliat pocaitu Data 7 martie 2007 02:06:45
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include<stdio.h>
#define infi 1005000
#define nmax 30005
#define valmax 1001
#define tip long long 
tip n,a1[nmax], u,l,a[nmax],b[nmax],sol;
void citire();void afisare();

void scade(tip k)
{tip i;
 for(i=1;i<=n;i++)
  a1[i]=a[i]-b[i]*k;
 }
int det_max()
{tip i,inc,max=-infi,coada=0,s=0,nr[nmax];
 nr[0]=0;
 for(i=1;i<=u;i++)
   s+=a1[i];
 max=s,coada=0,inc=1;
 for(i=u+1;i<=n;i++)
   {nr[++nr[0]]=i-u;
	coada+=a1[i-u];
	s-=a1[i-u];s+=a1[i];

	if(nr[inc]==i-l)
	 {coada-=a1[i-l];
	  inc++;
	  }

	if(coada<0)
	 {coada=0;
	  inc=nr[0]+1;
	  }

	if(s+coada>max)
	  max=s+coada;
	}
 if(max>0)
   return 1;
 if(max==0)
   return 0;
 return -1;
 }





void binar()
{tip r,ls=0,ld=valmax*102,mij;
 while(ld>ls)
  {mij=(ld+ls)/2;
   scade(mij);

   r=det_max();//det_max() returneaza 0 daca e gata -1 daca e mai mic si 1 daca e mai mare
   if(r==0)
	{sol=mij;return;}
   else
	if(r<0)
	  ld=mij-1;
	else
	  ls=mij+1;
	}
//sol=mij;
sol=ld;
}


int main()
{citire();
 binar();
 afisare();
 return 0;
 }

void afisare()
{
freopen("secv3.out","w",stdout);
 if(sol%100<10)
 printf("%lld.0%lld",sol/100,sol%100);
 else
	printf("%lld.%lld",sol/100,sol%100);
 }
void citire()
{tip i;
 freopen("secv3.in","r",stdin);
 scanf("%lld%lld%lld",&n,&u,&l);
 for(i=1;i<=n;i++)
  {scanf("%lld",&a[i]);
   a[i]*=100;
   }
 for(i=1;i<=n;i++)
  {scanf("%lld",&b[i]);
   //b[i]*=100;
   }

 }