Cod sursa(job #197238)

Utilizator alexeiIacob Radu alexei Data 2 iulie 2008 22:18:03
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include<stdio.h>
#define nmax 30024
#define Xmax 30000

double c[nmax],t[nmax];
double v[nmax];
double sum[nmax];
int h[nmax],poz[nmax];

int N,L,U;
    
void change(const int a,const int b)
{
     h[a]^=h[b];
     h[b]^=h[a];
     h[a]^=h[b];    
}
 
void upp(int stuff)  
{  
 int father=stuff>>1,ctrl=stuff;  
       
 if( father>=1 )  
     if( sum[h[father]]<sum[h[stuff]])  
     ctrl=father;  
   
 if( ctrl!=stuff )  
 {  
     change(ctrl,stuff);      
     int aux=poz[h[father]];  
       
   
     poz[h[father]]=poz[h[stuff]];  
     poz[h[stuff]]=aux;  
       
     upp(ctrl);  
       
 }  
   
}  
       
void down(int stuff)
{
int left=stuff<<1;
int right=left+1,ctrl=stuff;

if( left<=N )
{
    if( sum[ h[left] ]>sum[h[ctrl]] )
    ctrl=left;
    if( right<=N )
        if( sum[h[right]]>sum[h[ctrl]] )
        ctrl=right;

    if( ctrl!=stuff )
    {
        change(ctrl,stuff);
        poz[ h[ctrl] ]=ctrl;
        poz[ h[stuff] ]=stuff;
        
        down(ctrl);
    }
}
}



int main()
{
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    
    scanf("%d%d%d",&N,&L,&U);
    
    int i,a1,a2;
    
    for(i=1; i<=N; ++i)
    scanf("%lf",&c[i]);
    for(i=1; i<=N; ++i)
    scanf("%lf",&t[i]);
    
    double left=0,right=Xmax;
    double mij;
    int inc,sf;
    double solt;
    
    while( left<=right )
    {
           mij=(right+left)/2;
           sf=0;       
           
           for(i=1; i<=N; ++i){
           v[i]=c[i]-t[i]*mij;
           sum[i]=sum[i-1]+v[i];
           //printf("%f ",sum[i]);
           }
           //printf("\n");
           for(i=L; i<=U && i<=N; ++i){  
           h[++sf]=i;    
           poz[i]=sf;  
           upp(sf);  
           }         
           
           solt=sum[ h[1] ];  
           a2=N-L+1;  
           inc=L;  

           for(i=2; i<=a2; ++i){  
           poz[ h[sf] ]=poz[inc];  
           change( poz[inc], sf );  
           --sf;  
           down(poz[inc]);   
           ++inc;  
    
           if( i+U-1<=N )  
           {  
           ++sf;  
           h[sf]=i+U-1;  
           poz[i+U-1]=sf;   
           upp(sf);  
           }              
           a1=sum[h[1]]-sum[i-1];
           if( solt<a1 )
           solt=a1;
           
           }  
           if( solt>0 )
           right=mij-1;
           if( solt<0 )
           left=mij+1;
           if( !solt ){
           break;
           }
    }
    printf("%0.2lf\n",mij);
    
    return 0;
}