Cod sursa(job #2166869)

Utilizator ABBogdanBaicu Bogdan ABBogdan Data 13 martie 2018 19:17:27
Problema Secventa 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
int c[30010],t[30010],n,ls,ld,i,d[30010],l,u,sc[30010],s[30010];
double maxx,sum;
int main()
{
    f>>n>>l>>u;
    ls=0;
    ld=-1;
    maxx=-1;
    for(i=0;i<n;i++)
        {f>>c[i];
        sc[i]=sc[i-1]+c[i];
        }
    for(i=0;i<n;i++)
        {f>>t[i];
        s[i]=s[i-1]+t[i];
        }
    for(i=0;i<n;i++)
    {
      if(ls<=ld&&d[ls]<=i-u-1)
          ls++;
      if(i>=l)
      {
          while(ls<=ld&&(sc[i]-sc[i-l])/(s[i]-s[i-l])>=(sc[i]-sc[d[ld]])/(s[i]-s[d[ld]]))
              ld--;
          d[++ld]=i-l;
          sum=(double)(sc[i]-sc[d[ls]])/(double)(s[i]-s[d[ls]]);
          if(sum>maxx)
              maxx=sum;
      }
    }
    g<<fixed<<setprecision(2)<<maxx;
    return 0;
}