Cod sursa(job #3278654)

Utilizator Andrada_MincaAndrada Minca Andrada_Minca Data 20 februarie 2025 13:40:42
Problema Secventa 3 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
//
//  main.cpp
//  secventa3
//
//  Created by Andrada Minca on 20.02.2025.
//

#include <fstream>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
int n,l,u;
int c[30003],t[30003];
double v[30003];
double bs(double x)
{
    deque<int>dq;
    for(int i=1;i<=n;i++)
    {
        v[i]=c[i]-x*t[i];
    }
    double ans=-INT_MAX;
    int ri=0;
    for(int i=1;i<=n;i++)
    {
        while(ri<i-l)
        {
            ri++;
            while(!dq.empty()&&v[dq.front()]>v[ri])dq.pop_front();
            dq.push_front(ri);
        }
        while(!dq.empty() && dq.back()<=i-u) dq.pop_back();
        if(!dq.empty())
        ans=max(ans,v[i]-v[dq.back()]);
    }
    return ans;
}
int main()
{
    fin>>n>>l>>u;
    for(int i=1;i<=n;i++)
    {
        fin>>c[i];
        c[i]+=c[i-1];
    }

    for(int i=1;i<=n;i++)
    {
        fin>>t[i];
        t[i]+=t[i-1];
    }
    double st=0,dr=30003;
    double best=0;

    for(int i=0;i<=200;i++)
    {
        double mid=(st+dr)/2;
        if(bs(mid)>=0)st=mid,best=max(best,mid);
        else dr=mid;
    }

    fout<<fixed<<setprecision(2)<<best;
}