Cod sursa(job #347226)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 11 septembrie 2009 15:39:50
Problema Secventa 3 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
#include <values.h>
#define Nmax 30005

int c[Nmax],t[Nmax];
int n,L,U,sumt,sumc,st,dr,i,maxc,maxt;
int auxc,auxt,j,ok,auxst;

int update(){
	if ( sumc*maxt > sumt*maxc ){  // adica sumc/sumt > maxc/maxt
   	maxc = sumc, maxt=sumt;
      return 1;
   }
   return 0;
}


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

   sumc=0; sumt=0; maxt = MAXINT;
   for(st=dr=1; dr<=n; ){
   	sumc += c[dr]; sumt += t[dr];
      if(dr-st+1 > U ) sumc -= c[st], sumt -= t[st], st++;
      if(dr-st+1 >=L && dr-st+1 <=U){
         ok=0;
          auxst=st; auxc=sumc, auxt=sumt;
         update();
         while ( st<=dr && dr-st>=L){
         	sumc -= c[st], sumt -=t[st];
         	if( update() ) ok=1,auxc=sumc, auxt=sumt;
            st++;
         }
         if(!ok) sumc=auxc, sumt=auxt,st=auxst;
      }
      dr++;
   }

   printf("%.4f\n", (double)maxc/maxt);
   fclose(stdin); fclose(stdout);
   return 0;
}