Cod sursa(job #2976266)

Utilizator tudor_costinCostin Tudor tudor_costin Data 8 februarie 2023 19:35:43
Problema Secventa 3 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const int Nmax=30005;
int c[Nmax],t[Nmax],sc[Nmax],st[Nmax];
double ideal[Nmax];
deque<int> dq;
int main()
{
    int n,l,u;
    fin>>n>>l>>u;
    for(int i=1;i<=n;i++)
    {
        fin>>c[i];
        sc[i]=sc[i-1]+c[i];
    }
    for(int i=1;i<=n;i++)
    {
        fin>>t[i];
        st[i]=st[i-1]+t[i];
    }
    double left=0.0,r=1000.0;
    double mid,sol;
    while(left<r)
    {
        mid=(r+left)/2;
        int ok=0;
        for(int i=1;i<=n;i++)
        {
            ideal[i]=1.0*st[i]-(sc[i]/mid);
        }
        dq.clear();
        for(int i=l;i<=n;i++)
        {
            while(!dq.empty() && ideal[i-l]>ideal[dq.back()])
            {
                dq.pop_back();
            }
            dq.push_back(i-l);
            if(dq.front()<i-u)
            {
                dq.pop_front();
            }
            if(ideal[i]-ideal[dq.front()]==0)
            {
                ok=2;
                break;
            }
            if(ideal[i]-ideal[dq.front()]<=0)
            {
                ok=1;
            }
        }
        if(ok==2)
        {
            sol=mid;
            left=mid+1;
        }
        if(ok==1)
        {
            left=mid;
        }
        if(ok==0)
        {
            r=mid;
        }

    }
    fout<<sol;
    return 0;
}