Cod sursa(job #318240)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 27 mai 2009 18:49:56
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <stdio.h>

using namespace std;

#define maxn 30010
#define eps 0.001
long n, i, j, k, l, u, p1, p2, c[maxn], t[maxn], d[maxn], ok;
double left, right, mid, sol, v[maxn];

int main()
{
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);
    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]);
    }
    left=0;
    right=n*1000;
    while(left + eps <= right)
    {
        mid=(left+right)/2;
        ok=0;
        d[1]=0;
        p1=1;
        p2=1;
        for(i=1; i<=n; i++)
        {
            v[i]=v[i-1]+c[i]-t[i]*mid;
            if(i-d[p1]>u)
            {
                p1++;
            }
            if(i-l>=0)
            {
                while(v[d[p2]]>=v[i-l] && p2>=p1)
                {
                    p2--;
                }
                p2++;
                d[p2]=i-l;
                if(v[i]-v[d[p1]]>=0) ok=1;
            }           
        }
        if(ok)
        {
            sol=mid;
            left=mid+eps;
        }
        else
        {
            right=mid-eps;
        }
    }
    printf("%.2lf", sol);
    return 0;
}