Cod sursa(job #214299)

Utilizator alexeiIacob Radu alexei Data 13 octombrie 2008 20:26:06
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include<stdio.h>
#define NMAX 30024
double S[NMAX],T[NMAX];
int DEQ[NMAX];
//daca nici asa nu merge tre sa ma las de idei geniale si sa ma apuc 
//de debug la sursa de O(N*logN)
int i1,s1;
double a1,a2;
inline double max(const double a,const double b){ return a>b?a:b; } 

void read_init(const int N)
{
     int i;
     for(i=1; i<=N; ++i)
     {
              scanf("%lf",&S[i]);
              S[i]+=S[i-1];
     }
     for(i=1; i<=N; ++i)
     {
              scanf("%lf",&T[i]);
              T[i]+=T[i-1];
     }
}

inline bool comp(const int p1,const double V2)
{
       const double V1=(S[p1]-a1)/(T[p1]-a2);
       if( V1<=V2 )return 0;
       return 1;
}

void add(const double val,const int poz,const int K) 
{
     if( !i1 ){
         DEQ[i1=s1=1]=poz;return;}
     
     if( !comp(DEQ[s1],val) || DEQ[ s1 ]<K )
     {
         if( !comp(DEQ[i1],val) ){
             DEQ[i1=s1=1]=poz;return;}
                 
         while( !comp(DEQ[s1],val) || DEQ[s1]<K )
         --s1;
         DEQ[++s1]=poz;return;
     }
     
     DEQ[++s1]=poz;
}    

void erase(const int poz)
{
     while( DEQ[i1]<poz )++i1;
}

inline double calc(const int poz)
{
       return (S[poz]-a1)/(T[poz]-a2);
}

int main()
{
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    
    int N,L,U;
    scanf("%d%d%d",&N,&L,&U);
    
    read_init(N);
    
    double solfin,val;
    int i,j;
    for(i=L; i<=U; ++i)
    {
             val=S[i]/T[i];a1=a2=0;
             add(val,i,i-U+1); 
             solfin=max(solfin,val);
    }
    
    for(i; i<=N; ++i)
    {
           erase(i-U+1);
           a1=S[i-U];a2=T[i-U];
           val=(S[i]-a1)/(T[i]-a2);
           add(val,i,i-U+1);
           solfin=max(solfin,calc(DEQ[i1]));
    }
    
    for(j=N-U+1,i=N; i-j>=L; ++j)
    {
           erase(j+1);
           a1=S[j];a2=T[j];
           val=(S[N]-a1)/(T[N]-a2);
           solfin=max(solfin,calc(DEQ[i1]));
    }
    
    printf("%0.2lf\n",solfin);
    
    return 0;
}