Cod sursa(job #1257059)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 7 noiembrie 2014 10:26:50
Problema Secventa 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<fstream>
#include<deque>

using namespace std;

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

const int nmax = 30000;
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() {
    int m;
    fin >> n >> l >> u;
    for( int i = 1; i <= n; ++ i ) {
        fin >> a[ i ];
    }
    for( int i = 1; i <= n; ++ i ) {
        fin >> b[ i ];
    }
    m = 0;
    for( int step = 1 << 30; step > 0; step >>= 1 ) {
        if ( check( (double)(m + step) / 100 ) ) {
            m += step;
        }
    }
    fout << (double)m / 100 << "\n";
    fin.close();
    fout.close();
    return 0;
}