Cod sursa(job #347237)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 11 septembrie 2009 16:18:55
Problema Secventa 3 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>
#include <values.h>
#define Nmax 30005
#define ll long long

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 ( (ll)sumc*maxt >(ll) 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 = Nmax*10000;
   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){
          auxst=st; auxc=sumc, auxt=sumt;
         update();
         while ( st<=dr && dr-st>=L){
         	sumc -= c[st], sumt -=t[st];
            st++;
         	if( update() ) auxc=sumc, auxt=sumt,auxst=st;
         }
         sumc=auxc, sumt=auxt,st=auxst;
      }
      dr++;
   }

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