Cod sursa(job #2390040)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 27 martie 2019 18:36:39
Problema Secventa 3 Scor 0
Compilator cpp-64 Status done
Runda preoni21204 Marime 1.4 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);
    ans=SL[L]/(float)SC[L];
    for(int i=2;i<=N;i++)
    {
            if(!dq.empty()&&i-dq.front()==U) dq.pop_front();
            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);
                poz=dq.front();
                float rez=(SL[i]-SL[poz-1])/(float)(SC[i]-SC[poz-1]);
                ans=max(ans,rez);
            }
            else
            {
                dq.push_back(i);
                poz=dq.front();
                float rez=(SL[i]-SL[poz-1])/(float)(SC[i]-SC[poz-1]);
                ans=max(ans,rez);
            }

            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;
}