Cod sursa(job #2390016)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 27 martie 2019 18:11:55
Problema Secventa 3 Scor 10
Compilator cpp-64 Status done
Runda preoni21204 Marime 1.06 kb
#include <bits/stdc++.h>
#define Dim 30005
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
int N,L,U,SL[Dim],SC[Dim],A[Dim],B[Dim];
float ans;

deque < int > dq;

int main()
{
    f>>N>>L>>U;
    for(int i=1;i<=N;i++)
    {
        f>>A[i];
        SL[i]=SL[i-1]+A[i];
    }
    for(int i=1;i<=N;i++)
    {
        f>>B[i];
        SC[i]=SC[i-1]+B[i];
    }
    dq.push_back(1);
    for(int i=2;i<=N;i++)
    {
            int poz=dq.front();
            if(  (SL[i-1]-SL[poz-1])*(SC[i-1]-SC[poz])+A[1]*B[i] < (SL[i-1]-SL[poz])*(SC[i-1]-SC[poz-1])+B[1]*A[i]   )
            {
                dq.pop_front();
                dq.push_back(i);
            }
            else
            dq.push_back(i);

            while(dq.size()>U) dq.pop_front();

            if(dq.size()>=L&&dq.size()<=U)
            {
                poz=dq.front();
                float rez=(SL[i]-SL[poz-1])/(float)(SC[i]-SC[poz-1]);
                ans=max(ans,rez);
            }
    }
    g<<fixed<<setprecision(10)<<ans;
    return 0;
}