Cod sursa(job #2049399)

Utilizator dianamariaDiana Cataros dianamaria Data 27 octombrie 2017 09:36:34
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include <iomanip>
using namespace std;
ifstream in ("secv3.in");
ofstream out ("secv3.out");
const int N=30002;
int c[N],t[N],d[N];
int main()
{
    int n,l,u,i,st=1,dr=1;
    double maxi;
    in>>n>>l>>u;
    for (i=1;i<=n;i++)
        in>>c[i], c[i]+=c[i-1];
    for (i=1;i<=n;i++)
        in>>t[i], t[i]+=t[i-1];
    d[1]=1;
    maxi=(double)c[l]/t[l];
    for (i=l+1;i<=n;i++)
    {
        while (st<=dr && d[st]<=i-u)
            st++;
        while (st<=dr && (double)(c[i]-c[d[dr]-1])/(t[i]-t[d[dr]-1])<(double)(c[i]-c[i-l])/(t[i]-t[i-l]))
            dr--;
        dr++;
        d[dr]=i-l+1;
        if (maxi<(double)(c[i]-c[d[st]-1])/(t[i]-t[d[st]-1]))
            maxi=(double)(c[i]-c[d[st]-1])/(t[i]-t[d[st]-1]);
    }
    out<<setprecision(2)<<fixed<<maxi;
    return 0;
}