Cod sursa(job #3350495)

Utilizator CarenaMironov Cezar Luca Carena Data 8 aprilie 2026 19:36:23
Problema Secventa 3 Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include <iomanip>
#include <deque>

using namespace std;

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

const int NMAX=3e4+5;
const double PMAX=16777216, PMIN=0.00390625;
int n, l, u, x, sc[NMAX], st[NMAX];
deque<int> dq;

double func(int i, double r)
{
    return sc[i]-r*st[i];
}

bool check(double r)
{
    dq.clear();
    for(int j=1;j<=n-l+1;j++)
    {
        while(!dq.empty() && func(j-1, r)<=func(dq.front(), r))
            dq.pop_front();
        dq.push_front(j);
        while(!dq.empty() && dq.back()<j-u+l)
            dq.pop_back();
        if(!dq.empty() && func(dq.back()-1, r)<=func(j+l-1, r))
            return 1;
    }
    return 0;
}

double caut_bin()
{
    double r=0, pas=PMAX;
    while(pas>=PMIN)
    {
        if(check(r+pas))
            r+=pas;
        pas/=2;
    }
    return r;
}

int main()
{
    in>>n>>l>>u;
    for(int i=1;i<=n;i++)
    {
        in>>x;
        sc[i]=sc[i-1]+x;
    }
    for(int i=1;i<=n;i++)
    {
        in>>x;
        st[i]=st[i-1]+x;
    }
    out<<fixed<<setprecision(4)<<caut_bin();
    return 0;
}