Cod sursa(job #1606612)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 20 februarie 2016 13:42:15
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 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())
        {
        if(dq.front()==i-1)
        {
            s=s-co[i-1];
            t=t-ti[i-1];
            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();
        }
        for(j=j;j<pr+u && j<=n;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;
}