Cod sursa(job #638714)

Utilizator mihai995mihai995 mihai995 Data 21 noiembrie 2011 14:40:17
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
using namespace std;

const int N=30005;
const double E=1e-3;
int a[N],b[N],dq[N],n,L,U,st,dr;
double val[N];

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

inline void pop(int x)
{
    if (dq[st]==x)
        st++;
}

void push(int x)
{
    while (st<=dr && val[dq[dr]]>=val[x])
        dr--;
    dq[++dr]=x;
}

bool ok(double x)
{
    int i;
    st=1,dr=0;
    for (i=1;i<=n;i++)
        val[i]=val[i-1]+a[i]-b[i]*x;
    for (i=L;i<=n;i++)
    {
        pop(i-U-1);
        push(i-L);
        if (val[dq[st]]<=val[i])
            return true;
    }
    return false;
}

double bs()
{
    double i,step=512;
    for (i=0;E<=step;step/=2)
        if (ok(i+step))
            i+=step;
    return (double)((int)(i*100))/100;
}

int main()
{
    in>>n>>L>>U;
    for (int i=1;i<=n;i++)
        in>>a[i];
    for (int i=1;i<=n;i++)
        in>>b[i];
    out<<bs()<<"\n";
    return 0;
}