Cod sursa(job #1229651)

Utilizator george_stelianChichirim George george_stelian Data 17 septembrie 2014 21:30:12
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int n,x,y,i;
double c[30010],t[30010],st,dr,mid;

int existasubsir(double avarage)
{
    double v[30010],sol;
    int v1[30010],i,a,b;
    v[0]=0;
    for(i=1;i<=n;i++) v[i]=v[i-1]+c[i]-t[i]*avarage;
    sol=v[x];
    a=b=1;
    v1[1]=1;
    for(i=x+1;i<=n;i++)
    {
        if(v1[a]==i-y-1) a++;
        while(a<=b && v[i-x]<=v[v1[b]]) b--;
        v1[++b]=i-x;
        sol=max(sol,v[i]-v[v1[a]]);
    }
    return sol>=0;
}

int main()
{
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);
    scanf("%d%d%d",&n,&x,&y);
    for(i=1;i<=n;i++) scanf("%lf",&c[i]);
    for(i=1;i<=n;i++) scanf("%lf",&t[i]);
    st=0.01;dr=30000000;
    while(dr-st>=0.001)
    {
        mid=(st+dr)/2;
        if(existasubsir(mid)) st=mid+0.001;
        else dr=mid-0.001;
    }
    printf("%.2lf",dr);
    return 0;
}