Cod sursa(job #1393337)

Utilizator patrutoiuandreipatrutoiu andrei patrutoiuandrei Data 19 martie 2015 12:18:19
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>

using namespace std;

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

int i, n, l,u,dq[30100],c[30100],t[30100];
double s[30100], st, dr, mij, sol;

int secv(double r)
{
    for(i=1;i<=n;i++)
    {
        s[i]=s[i-1]+c[i]-r*t[i];
    }
    int st=1,dr=1;
    dq[1]=0;
    for(i=1;i<=n;i++)
    {
        while(st<=dr&&s[i]-s[dq[dr]]<0.001)
            dr--;
        dq[++dr]=i;
        while(dr-st>u)
            st++;
        if(dr-st>=l)
        {
            if(s[dq[dr]]-s[dq[st]]>0.001)
                return 1;
        }
    }
    return 0;
}
int main()
{
    fin>>n>>l>>u;
    for(i=1;i<=n;i++)
        fin>>c[i];
    for(i=1;i<=n;i++)
        fin>>t[i];
    st=0;dr=2000000000;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(secv(mij))
        {
            sol=mij;
            st=mij+0.001;
        }
        else
            dr=mij-0.001;
    }
    fout<<sol;
    return 0;
}