Cod sursa(job #952677)

Utilizator primulDarie Sergiu primul Data 23 mai 2013 19:52:09
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<fstream>
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
int i,n,l,r,a[30010],b[30010],d[30010];
double mij,li,sol,ls,s[30010];
int verif(double x)
{
    int p,u,i;
    for(i=1;i<=n;++i)
    s[i]=s[i-1]+a[i]-(double)b[i]*x;
    p=1;
    u=0;
    for(i=l;i<=n;++i)
    {
        while(p<=u&&d[p]==i-r)
        ++p;
        while(p<=u&&s[i-l]<s[d[u]])
        --u;
        ++u;
        d[u]=i-l;
        if(s[i]>s[d[p]])
        return 1;
    }
    return 0;
}
int main()
{
    f>>n>>l>>r;
    for(i=1;i<=n;++i)
    f>>a[i];
    for(i=1;i<=n;++i)
    f>>b[i];
    li=0;
    ls=1<<28;
    while(li<=ls)
    {
        mij=(li+ls)/2;
        if(verif(mij))
        sol=mij,li=mij+0.001;
        else
        ls=mij-0.001;
    }
    g<<sol<<'\n';
    return 0;
}