Cod sursa(job #203379)

Utilizator alexeiIacob Radu alexei Data 15 august 2008 22:55:15
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include<stdio.h>
#define nmax 120024 
#define nmic 30024
//pare nefinisata
double arb[nmax];
double a[nmic],b[nmic],c[nmic];
int target;
double value;

inline double min(const double a,const double b)
{
       if( a<b )
       return a;
       return b;
}

inline double abs(const double value)
{
       if( value>=0 )
       return value;
       return -value;
}
       
void update(int nod,int left,int right)
{
     if( left==right ){    
         arb[nod]=value;
         return;
     }
     
     int mij=(left+right)>>1;
     int hope=2*nod;
     
     if( target<= mij ) update( hope, left, mij);
     else               update( hope+1, mij+1, right);
     
     if( abs(arb[hope]) < abs(arb[hope+1]) )
     arb[nod]=arb[hope];
     else
     arb[nod]=arb[hope+1];
     
}

int main()
{
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    
    int N,L,U;
    scanf("%d%d%d",&N,&L,&U);

    int i,a1;
    for(i=1; i<=N; ++i)
    scanf("%lf",&a[i]);
 
    for(i=1; i<=N; ++i)
    scanf("%lf",&b[i]);
    
    double left=0,right=30000,mij;
    double best=1,bestm,a2=N-L+1;
    int takka=0;
    double kk,solfin=0;
    
    while( left<=right )
    {
           mij=(left+right)/2;
           
           for(i=1; i<=N; ++i){
           c[i]=a[i]-b[i]*mij;
           target=i; value=c[i];
           update(1,1,N);
           }
    
           for(i=L; i<=U && i<=N; ++i)
           {
                    target=i; value=c[i]; 
                    update( 1,1,N );
           }

           best=abs(arb[1]);
           bestm=arb[1];
           
           for(i=2; i<=a2; ++i){
           
                target=i-1;value=nmax;
                update( 1,1,N );    
           
                a1=i+U-1;
           
                if( a1<=N )
                {
                    target=a1; value=c[a1];
                    update( 1,1,N );
                }
                kk=abs(arb[1]);
                
                if( kk<best )
                best=kk,bestm=arb[1];
                
           }
           
           if( best<=0.01 ){
               if( mij-solfin<=0.01 )
               break;
               
           solfin=mij;    
           left=mij,right=30000;
           continue;
           }
           if( bestm>0 )
           left=mij;
           else
           right=mij;
}

printf("%0.2lf\n",solfin);

return 0;
}