Cod sursa(job #1824046)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 7 decembrie 2016 11:14:03
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <deque>
#include <iomanip>

using namespace std;

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

const int NMAX = 30010;

deque<pair<double, int>> d;

int N, L, R;
int a[NMAX], b[NMAX];
double dist[NMAX];

bool check (double x) {
    for (int i = 1; i <= N; i++) {
        dist[i] = dist[i - 1] + 1.00 * a[i] - x * b[i];
    }

    while (!d.empty())
        d.pop_back();

    for (int i = 1; i <= N; i++) {
        while (!d.empty() && d.front().second < i - R + 1) {
            d.pop_front();
        }
        if (i >= L) {
            while (!d.empty() && d.back().first > dist[i - L]) {
                d.pop_back();
            }
            d.push_back(make_pair(dist[i - L], i - L));
        }
        if (i >= L && !d.empty() && dist[i] - d.front().first >= 0.0) {
            return true;
        }
    }
    return false;
}

int main () {
    fin >> N >> L >> R;
    for (int i = 1; i <= N; i++) {
        fin >> a[i];
    }
    for (int i = 1; i <= N; i++) {
        fin >> b[i];
    }

    double left = 0, right = 1000;
    for (int i = 1; i <= 20; i++) {
        double mid = (left + right) / 2;

        if (check (mid)) {
            left = mid;
        }
        else {
            right = mid;
        }
    }

    fout << fixed << setprecision (2) << left;

    return 0;
}