Cod sursa(job #300653)

Utilizator DraStiKDragos Oprica DraStiK Data 7 aprilie 2009 16:25:56
Problema Secventa 3 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
#define DIM 3005
#define INF 1<<31-1
int c[DIM],t[DIM],q[DIM];
int n,l,u;
double a[DIM];
void read ()
{
    int i;
    scanf ("%d%d%d",&n,&l,&u);
    for (i=1; i<=n; ++i)
        scanf ("%d",&c[i]);
    for (i=1; i<=n; ++i)
        scanf ("%d",&t[i]);
}
double rez (double val)
{
    double max=-INF;
    int i,st=1,dr=1;
    for (i=1; i<=n; ++i)
        a[i]=(double)(a[i-1]+c[i]-t[i]*val);
    q[1]=0;
    for (i=l; i<=n; ++i)
    {
        if (a[i]-a[q[st]]>max)
            max=a[i]-a[q[st]];
		while (a[q[dr]]>=a[i-l+1] && st<=dr)
            --dr;
		q[++dr]=i-l+1;
		if (q[st]==i-u)
            ++st;
	}
	return max;
}
void solve ()
{
    double st=0,dr=1000,mij,nr;
    while (dr-st>0.001)
    {
        mij=(st+dr)/2;
        nr=rez (mij);
        if (nr==0)
            st=dr=mij;
        else if (nr>0)
            st=mij+0.001;
        else
            dr=mij-0.001;
    }
    printf ("%.2f",dr);
}
int main ()
{
    freopen ("secv3.in","r",stdin);
    freopen ("secv3.out","w",stdout);
    read ();
    solve ();
    return 0;
}