Cod sursa(job #1253731)

Utilizator Athena99Anghel Anca Athena99 Data 1 noiembrie 2014 18:49:01
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <deque>
#include <fstream>
#include <iomanip>

using namespace std;

ifstream fin("secv3.in");
ofstream fout("secv3.out");

const double dif= 0.001;
const int inf= (1<<30)-1+(1<<30);
const int nmax= 30000;
const int out_precision= 2;

double sol;
double a[nmax+1], b[nmax+1], spc[nmax+1];

int n, u, l;

int check( double x ) {
    for ( int i= 1; i<=n; ++i ) {
        spc[i]= spc[i-1]+a[i]-x*b[i];
    }

    deque <int> d;
    for ( int i= 1; i<=n; ++i ) {
        for ( ; !d.empty() && spc[i-1]<=spc[d.back()-1]; d.pop_back() ) ;
        d.push_back(i);
        if ( d.front()==i-u ) d.pop_front();

        if ( spc[i]>spc[d.front()-1] ) {
            return 1;
        }
    }

    return 0;
}

int main(  ) {
    fin>>n>>l>>u;
    for ( int i= 1; i<=n; ++i ) {
        fin>>a[i];
    }
    for ( int i= 1; i<=n; ++i ) {
        fin>>b[i];
    }

    double left= 0, right= inf, mid;
    while ( left<=right ) {
        mid= ((double)left+right)/2;
        if ( check(mid) ) {
            sol= mid;
            left= mid+dif;
        } else {
            right= mid-dif;
        }
    }

    fout<<setprecision(out_precision)<<fixed;
    fout<<sol<<"\n";

    return 0;
}