Cod sursa(job #2215144)

Utilizator felixiPuscasu Felix felixi Data 21 iunie 2018 10:24:42
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 30000;
const int VMAX = 1000;

double vals[NMAX+2], a[NMAX+2], b[NMAX+2];
int N, L, H;

bool OK(double M)
{
    for( int i = 1;  i <= N;  ++i )
        vals[i] = vals[i - 1] + a[i] - M * b[i];
    deque<int> dq;
    for( int i = 1, st = i - H, dr = i - L;  i <= N;  ++i, ++st, ++dr ) {
        if( dr >= 0 ) {
            while( !dq.empty() && vals[ dq.back() ] >= vals[dr] )
                dq.pop_back();
            dq.push_back(dr);
        }
        if( st >= 0 ) {
            while( !dq.empty() && dq.front() < st )
                dq.pop_front();
        }
        if( !dq.empty() && vals[i] >= vals[ dq.front() ] )
            return 1;
    }
    return 0;
}

int main()
{
    in >> N >> L >> H;
    for( int i = 1;  i <= N;  ++i ) in >> a[i];
    for( int i = 1;  i <= N;  ++i ) in >> b[i];
    double st = 1e-3, dr = VMAX * NMAX, best = 0;
    for( int step = 0;  step < 60;  ++step ) {
        double mid = (st + dr) / 2.0;
        if( OK(mid) ) {
            best = mid;
            st = mid;
        }
        else
            dr = mid;
    }
    out << setprecision(2) << fixed << best << '\n';
    return 0;
}