Cod sursa(job #2094633)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 26 decembrie 2017 12:39:37
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <deque>
#include <iomanip>
#include <cmath>

using namespace std;

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

const int nmax = 3e4;
const double eps = 1e-3;

int n, l, u;
int a[nmax + 1], b[nmax + 1];
double v[nmax + 1];

deque< int > d;

bool check (double val) {
    for (int i = 0; i <= n; ++ i) {
        v[ i ] = (double)a[ i ] - val * b[ i ];
    }

    d.clear();
    for (int i = l; i <= n; ++ i) {
        while (!d.empty() && v[ d.back() ] >= v[i - l]) {
            d.pop_back();
        }
        d.push_back(i - l);

        if (d.front() < i - u) {
            d.pop_front();
        }

        if (v[ i ] >= v[ d.front() ]) {
            return 1;
        }
    }
    return 0;
}

int main () {
    fin >> n >> l >> u;

    for (int i = 1; i <= n; ++ i) {
        int x;
        fin >> x;
        a[ i ] = a[i - 1] + x;
    }

    for (int i = 1; i <= n; ++ i) {
        int x;
        fin >> x;
        b[ i ] = b[i - 1] + x;
    }

    double x, y;
    x = 1 / 3e7; y = 3e7;

    while (fabs(x - y) >= eps) {
        double mij = (x + y) / 2;

        if (check( mij )) {
            x = mij;
        } else {
            y = mij;
        }
    }

    fout << setprecision( 5 ) << fixed;
    fout << x << "\n";

    fin.close();
    fout.close();
    return 0;
}