Cod sursa(job #2743942)

Utilizator DragosC1Dragos DragosC1 Data 23 aprilie 2021 18:38:44
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
#include <iostream>
#include <deque>
#include <iomanip>
using namespace std;

int L, R, n;
int c[30101];
int t[30101];
double val[30101];
double rez = 0;
const double EPS = 1e-4;

void read() {
    int i;
    ifstream f("secv3.in");
    f >> n >> L >> R;
    for (i = 1; i <= n; i++) {
        f >> c[i];
        c[i] += c[i - 1];
    }
    for (i = 1; i <= n; i++) {
        f >> t[i];
        t[i] += t[i - 1];
    }
    f.close();
}

deque<int> dq;

bool check(double x) {
    int i;
    for (i = 1; i <= n; i++)
        val[i] = 1.0 * c[i] - 1.0 * t[i] * x;
    dq.clear();
    for (i = L; i <= n; i++) {
        while (dq.size() > 0 && val[dq.back()] >= val[i - L]) 
            dq.pop_back();
        dq.emplace_back(i - L);
        if (i - dq.front() == R)
            dq.pop_front();
        if (val[i] - val[dq.front()] >= 0.0)
            return 1;
    }
    return 0;
}

void solve() {
    int i;
    double st = 0.0, dr = 1000.0, mij;
    while (dr - st > EPS) {
        mij = (st + dr) / 2;
        if (check(mij)) {
            rez = mij;
            st = mij + EPS;
        }
        else dr = mij - EPS;
    }
}

void output() {
    ofstream g("secv3.out");
    g << setprecision(2) << fixed << rez;
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}