Cod sursa(job #2820517)

Utilizator Gabriel_DascalescuGabriel Dascalescu Gabriel_Dascalescu Data 20 decembrie 2021 16:53:24
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <deque>
#include <iomanip>
#define nmax 30005
#define prec 1e-3

using namespace std;

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

double c[nmax], t[nmax], v[nmax], sp[nmax];
int  n, l, u;

deque <int> de;

bool verific(double x)
{
    for(int i=1; i<=n; i++)
    {
        v[i] = c[i] - x * t[i];
    }
    for(int i=1; i<=n; i++)
    {
        sp[i] = sp[i-1] + v[i];
    }
    de.clear();
    for(int i=l; i<=n; i++)
    {
        while(de.empty() != 1 && sp[i-l] <= sp[de.back()] )
        {
            de.pop_back();
        }
        de.push_back(i-l);
        if(de.front() == i - u -1)
        {
            de.pop_back();
        }
        if(sp[i] > sp[de.front()])
            return 1;
    }
    return 0;
}

double bs()
{
    double st, dr, med;
    st = 0;
    dr = 1000;
    while(st<=dr)
    {
        med = (st+dr)/2;
        if(verific(med) == 0)
            dr = med - prec;
        else
            st = med + prec;
    }
    return med;
}

int main()
{
    in>>n>>l>>u;
    for(int i=1; i<=n; i++)
    {
        in>>c[i];
    }
    for(int i=1; i<=n; i++)
    {
        in>>t[i];
    }
    out<<setprecision(2)<<fixed<<bs();
    return 0;
}