Cod sursa(job #2566188)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 2 martie 2020 19:22:50
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <iomanip>
#include <deque>

#define NMAX 30005
#define EPS 0.00001
using namespace std;

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

int t[NMAX], c[NMAX], n, l, r;
double vec[NMAX];
deque<int> dq;

bool test(double val){
    for(int i = 1; i <= n; ++i)
        vec[i] = c[i] - t[i] * val;
    dq.clear();
    for(int i = l; i <= n; ++i){
        while(!dq.empty() && i - dq.front() + 1 > r)
            dq.pop_front();
        while(!dq.empty() && vec[dq.back()] >= vec[i - l])
            dq.pop_back();
        dq.push_back(i - l);

        if(vec[i] - vec[dq.front()] >= 0)
            return 1;
    }
    return 0;
}

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

    for(int i = 1; i <= n; ++i)
        fin >> c[i];
    for(int i = 1; i <= n; ++i)
        fin >> t[i];

    for(int i = 1; i <= n; ++i)
        t[i] += t[i - 1], c[i] += c[i - 1];

    double st = 0.0, dr = 1000.0, best;
    while(dr - st >= EPS){
        double mij = (st + dr) / 2.0;
        if(test(mij)){
            best = mij;
            st = mij;
        }
        else dr = mij   ;
    }

    fout << fixed << setprecision(2) << best << '\n';
    return 0;
}