Cod sursa(job #2905774)

Utilizator cincadavidCinca David Andrei cincadavid Data 23 mai 2022 18:26:50
Problema Secventa 3 Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <deque>
#include <iomanip>

using namespace std;

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

int a[100001];
int b[100001];
int q[100001];

int main()
{
    int n,l,r;
    cin>>n>>l>>r;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    for(int i=1;i<=n;i++)
    {
        a[i]+=a[i-1];
        b[i]+=b[i-1];
    }
    double maxx=(double)(a[l])/b[l];
    int p=r=1;
    q[1]=1;
    for(int i=l+1;i<=n;i++)
    {
        while(p<=r && q[i]<=i-r)
        {
            p++;
        }
        while(p<=r && (double)(a[i]-a[q[r]-1])/(b[i]-b[q[r]-1])<(double)(a[i]-a[i-l])/(b[i]-b[i-l]))
        {
            r--;
        }
        r++;
        q[r]=i-l+1;
        maxx=max(maxx,(double)(a[i]-a[q[p]-1])/(b[i]-b[q[p]-1]));
    }
    cout<<maxx;

    return 0;
}