Cod sursa(job #1260464)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 11 noiembrie 2014 12:34:09
Problema Secventa 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<fstream>
#include<deque>
#include<iomanip>

using namespace std;

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

const int nmax = 30000;
const double eps = 0.001;
const int inf = 1 << 30;
int n, u, l;
double a[ nmax + 1 ], b[ nmax + 1 ], c[ nmax + 1 ];

deque <int> d;

bool check( double x ) {
    d.clear();
    for( int i = 1; i <= n; ++ i ) {
        c[ i ] = c[ i - 1 ] + a[ i ] - x * b[ i ];
    }
    for( int i = 1; i <= n - l; ++ i ) {
        while ( !d.empty() && c[ d.back() ] > c[ i ] ) {
            d.pop_back();
        }
        d.push_back( i );

        if ( d.front() < i - u + l ) {
            d.pop_front();
        }
        if ( i - u + l > 0 ) {
            if ( c[ i + l ] > c[ d.front() ] ) {
                return 1;
            }
        }
    }
    return 0;
}
int main() {
    double st, dr, mid;
    fin >> n >> l >> u;
    for( int i = 1; i <= n; ++ i ) {
        fin >> a[ i ];
    }
    for( int i = 1; i <= n; ++ i ) {
        fin >> b[ i ];
    }
    st = 0; dr = inf;
    while ( st <= dr ) {
        mid = (st + dr) / 2;
        if ( check( mid ) ) {
            st = mid + eps;
        } else {
            dr = mid - eps;
        }
    }
    fout << setprecision( 3 ) << fixed;
    fout << mid << "\n";
    fin.close();
    fout.close();
    return 0;
}