Cod sursa(job #2095188)

Utilizator VasilescuVasilescu Eliza Vasilescu Data 27 decembrie 2017 09:33:32
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("secv3.in");
ofstream fout("secv3.out");

struct dream
{
    double a,b;
};
dream v[30005];

int  h[30005];
double maxx;

int main()
{
    int i,frecv,k, n, l, u;
    fin>>n>>l>>u;

    for(i=1; i<=n; ++i)
    {
        fin>>v[i].a;
        v[i].a+=v[i-1].a;
    }
    for(i=1; i<=n; ++i)
    {
        fin>>v[i].b;
        v[i].b+=v[i-1].b;
    }
    frecv=1;
    k=0;
    maxx=v[l].a/v[l].b;

    for(i=l; i<=n; ++i)
    {
        while(frecv<=k && (v[i].a-v[h[k]].a)/(v[i].b-v[h[k]].b)<(v[i].a-v[i-l].a)/(v[i].b-v[i-l].b ))
            --k;

        h[++k]=i-l;
        if(i>u)
            if(h[frecv]==i-u-1)
                ++frecv;

        if(h[frecv]==0)
        {
            if(maxx< v[i].a/v[i].b)
                maxx=v[i].a/v[i].b;
        }
        else if(maxx< (v[i].a-v[h[frecv]].a)/(v[i].b-v[h[frecv]].b))
            maxx=(v[i].a-v[h[frecv]].a)/(v[i].b-v[h[frecv]].b);
    }

    fout<<maxx;

    return 0;
}