Cod sursa(job #2905185)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 20 mai 2022 08:21:01
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <iomanip>
#include <deque>

using namespace std;

const int MAX_N = 3 * 1e4;
int a[MAX_N + 1], t[MAX_N + 1];
double tmp[MAX_N + 1];
int n, l, u;

bool ok(double x) {
    deque<int> dq;
    tmp[0] = 0;
    for (int i = 1; i <= n; i++) {
        tmp[i] = tmp[i - 1] + a[i] - x * t[i];
        if (i >= l) {
            if (!dq.empty() && dq.front() == i - u + 1) {
                dq.pop_front();
            }
            while (!dq.empty() && tmp[i - l] <= tmp[dq.back()]) {
                dq.pop_back();
            }
            dq.push_back(i - l);
            if (tmp[i] - tmp[dq.front()] >= 0) {
                return true;
            }
        }
    }
    return false;
}

double cb() {
    double st = 0, dr = (1 << 20), sol = 0;
    for (int pas = 1; pas <= 100; pas++) {
        double mijl = (st + dr) / 2;
        if (ok(mijl)) {
            sol = mijl;
            st = mijl;
        } else {
            dr = mijl;
        }
    }
    return sol;
}

int main() {
    ifstream fin("secv3.in");
    ofstream fout("secv3.out");
    fin >> n >> l >> u;
    for (int i = 1; i <= n; i++) {
        fin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        fin >> t[i];
    }
    double answer = cb();
    fout << setprecision(2) << fixed << answer;
    return 0;
}