Cod sursa(job #347261)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 11 septembrie 2009 17:25:05
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#define Nmax 30005
#define ll long long

int c[Nmax],t[Nmax];
int n,i,U,L,st,dr,x,sol,p,u;
int q[Nmax];
ll s[Nmax],a[Nmax],max,aux;

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",&c[i]),c[i]*=100;
   for(i=1;i<=n;++i) scanf("%d",&t[i]);

   st=0; dr=100000; s[0]=0;
   while( st<=dr ){
   	x=st+(dr-st)/2;
      for(i=1;i<=n;++i){
      	 a[i]=c[i]-t[i]*x;
          s[i]=s[i-1]+a[i];
      }
      max=s[L];
      p=u=1; q[1]=1; // deque
      for(i=L+1; i<=n; ++i){
      	if(i-q[p]+1 > U) p++;
         aux=s[i]-s[i-L];
         while( aux> s[i]-s[q[u]-1] && u>=p ) u--;
         q[++u]=i-L+1;
         aux=s[i]-s[q[p]-1];
         if(aux>max) max=aux;
      }
      if(max >=0) sol=x, st=x+1;
      else dr=x-1;
   }

   printf("%d.",sol/100);
   sol %=100;
   if(sol<10) printf("0");
   printf("%d",sol);
   fclose(stdin); fclose(stdout);
   return 0;
}