Cod sursa(job #912642)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 12 martie 2013 17:37:44
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<cstdio>
#include<deque>
 
#define MAX 100005
 
#define nmax 30005
 
using namespace std;
 
deque < int > dq;
 
int n,l,u;
short int c[nmax],t[nmax];
double result;  
 
void read( void )
{
    freopen("secv3.in","r",stdin);
    scanf("%d%d%d",&n,&l,&u);
    for(int i(1); i <= n ; ++i )
        scanf("%d",&c[i]);
    for(int i(1); i <= n ; ++i )
        scanf("%d",&t[i]);
    fclose(stdin);
}
 
bool check ( double m )
{
     
    double s[nmax];
         
    s[0]=0;
     
    dq.clear();
     
    for(int i(1) ; i <= n ; ++i )
        s[i]=s[i-1]+(double)c[i]-m*1.0*t[i];
     
    for(int i(l) ; i <= n ; ++i )
 
    {
        while(!dq.empty() && s[ dq.back() ] >= s[i-l+1])
            dq.pop_back();
         
        dq.push_back( i-l+1 );
         
        while(    i - dq.front() >=  u+1  )
            dq.pop_front();
         
        if(  s[i] - s[dq.front()]   > 0 )
            return true;    
         
    }       
        return false;
}
 
double solve ( void )
{
    double lo=0;
    double hi=MAX;
 
    while( hi-lo > 0.0001 )
    {
        double mid=(hi+lo)/2;
         
        if( check( mid )  )
        {
            result=mid;
            lo=mid+0.0001;
             
        }
        else
        {
             
            hi=mid-0.0001;
             
        }
         
         
         
         
         
    }
     
    return result;
     
}
void write( void )
{
    freopen("secv3.out","w",stdout);
    if(l <= u && l!=u )
    printf("%.4lf\n",solve());
    fclose(stdout);
}
 
 
 
int main()
{
    read();
     
    write();
    return 0;   
}