Cod sursa(job #1606583)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 20 februarie 2016 13:17:01
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include<cstdio>
#include<algorithm>
#include<deque>
using namespace std;
const int nmax=30000;
deque<int> dq;
double co[nmax+5],ti[nmax+5],sc[nmax+5],st[nmax+5];
int main()
{
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    int n,l,u,i,j,la,pr,q;
    bool ok;
    double ans,md,s,t,le,ri;
    scanf("%d%d%d",&n,&l,&u);
    for(i=1;i<=n;i++)
    {
        scanf("%lf",&co[i]);
        sc[i]=sc[i-1]+co[i];
    }
    for(i=1;i<=n;i++)
    {
        scanf("%lf",&ti[i]);
        st[i]=st[i-1]+ti[i];
    }
    le=0;
    ri=1000;
    for(q=1;q<=1000;q++)
    {
        md=(le+ri)/2;
        while(!dq.empty())
            dq.pop_back();
j=1;
s=t=0;
ok=0;
    for(i=1;i<=n;i++)
    {
        if(!dq.empty())
        {
            s=s-co[dq.front()];
            t=t-ti[dq.front()];
        if(dq.front()<i)
            dq.pop_front();

        }
        while(dq.size()<l)
        {
            dq.push_back(j);
            s=s+co[j];
            t=t+ti[j];
            j++;
        }
        if(!dq.empty())
        {
            pr=dq.front();
            la=dq.back();
        }
        else
        {
            pr=i-1;
            la=i-1;
        }
        for(j=j;j<=pr+u;j++)
        if((sc[j]-sc[la])/(st[j]-st[la])>=md)
        {
            s=s+sc[j]-sc[la];
            t=t+st[j]-st[la];
            dq.push_back(j);
            la=dq.back();
        }
        if(l<=dq.size() && dq.size()<=u)
        {
         if(s/t>=md)
             ok=1;
        }

    }
    if(ok)
    {
        ans=md;
        le=md;
    }
    else
        ri=md;
    }
    printf("%.2lf\n",ans);
    return 0;
}