Cod sursa(job #2474543)

Utilizator vladcoroian2001Vlad Coroian vladcoroian2001 Data 15 octombrie 2019 15:14:56
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fi("secv3.in");
ofstream fo("secv3.out");
const int NMAX=30005;
const double eps=1e-3;
int n,l,u,s[NMAX],t[NMAX],x[NMAX],y[NMAX];
double st,dr,mij,v[NMAX],sol;
deque <int> D;
int ok(double c)
{
    D.clear();
    for(int i=1;i<=n;i++)
        v[i]=(double)s[i]-(double)t[i]*c;
    for(int i=l;i<=n;i++)
    {
        if(!D.empty() && D.front()<i-u) D.pop_front();
        while(!D.empty() && v[i-l]<=v[D.back()]) D.pop_back();
        D.push_back(i-l);
        if(v[i]-v[D.front()]>=0) return 1;
    }
    return 0;
}
int main()
{
    fi>>n>>l>>u;
    for(int i=1;i<=n;i++)
    {
        fi>>x[i];
        s[i]=x[i]+s[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        fi>>y[i];
        t[i]=y[i]+t[i-1];
    }
    st=0; dr=1000;
    while(dr-st>=eps)
    {
        mij=(st+dr)/2;
        if(ok(mij))
        {
            sol=mij;
            st=mij;
        }
        else dr=mij;
    }
    fo<<fixed<<setprecision(2)<<sol;
    fi.close();
    fo.close();
    return 0;
}