Cod sursa(job #2077331)

Utilizator Garen456Paun Tudor Garen456 Data 27 noiembrie 2017 21:57:23
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
struct vis
{ double a,b;
};
vis v[30005];
int n,l,u;
int  h[30005];
double maxi;
int main()
{
    fin>>n>>l>>u;
    int i,fr,bc;

    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;}
    fr=1; bc=0;
    maxi=v[l].a/v[l].b;

    for(i=l;i<=n;++i)
    {
     while(fr<=bc && (v[i].a-v[h[bc]].a)/(v[i].b-v[h[bc]].b)<(v[i].a-v[i-l].a)/(v[i].b-v[i-l].b )) --bc;
     h[++bc]=i-l;
     if(i>u)
        if(h[fr]==i-u-1)
            ++fr;

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

    return 0;
}