Cod sursa(job #2563588)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 1 martie 2020 12:42:33
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 30005;
const double EPS = 1e-3;
ifstream in ("secv3.in");
ofstream out("secv3.out");
int n, l, u;
int spa[NMAX];
int spb[NMAX];
double val[NMAX];
bool ok(double x) {
    deque <int> dq;
    for(int i = 1; i <= n; i++) {
        val[i] = (double)spa[i] - ((double)spb[i]) * x;
    }
    for(int i = l; i <= n; i++) {
        while(!dq.empty() && i - dq.front() + 1 > u) {
            dq.pop_front();
        }
        while(!dq.empty() && val[dq.back()] >= val[i - l]) {
            dq.pop_back();
        }
        dq.push_back(i - l);
        if(val[i] - val[dq.front()] >= 0) {
            return 1;
        }
    }
    return 0;
}

int main() {
    in >> n >> l >> u;
    for(int i = 1; i <= n; i++) {
        in >> spa[i];
        spa[i] += spa[i - 1];
    }
    for(int i = 1; i <= n; i++) {
        in >> spb[i];
        spb[i] += spb[i - 1];
    }
    double st = 0, dr = 1000, last = 0;
    while(dr - st >= EPS) {
        double mij = (st + dr) / 2;
        if(ok(mij) == 1) {
            st = mij;
            last = mij;
        }
        else {
            dr = mij;
        }
    }
    out << fixed << setprecision(2) << last << "\n";
    return 0;
}