Cod sursa(job #1606809)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 20 februarie 2016 16:22:44
Problema Secventa 3 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
const int nmax=30000;
deque<int> dq;
long long co[nmax+5],ti[nmax+5],sp[nmax+5];
int main()
{
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    int n,l,u,i,j,la,pr,q,x;
    bool ok;
    long long ans,md,s,t,le,ri;
    cin>>n>>l>>u;
    for(i=1;i<=n;i++)
    {
        cin>>co[i];
        co[i]=co[i]*100;
    }
    for(i=1;i<=n;i++)
    {
        cin>>ti[i];
    }
    le=0;
    ri=100000;
    while(le<=ri)
    {
        ok=0;
        md=(le+ri)/2;
        for(i=1;i<=n;i++)
            sp[i]=sp[i-1]+co[i]-ti[i]*md;
    dq.clear();
        for(i=1;i<=n;i++)
        {
            while(!dq.empty())
            {
            if(i-dq.front()>=u)
                dq.pop_front();
                else
                    break;
            }
            if(!dq.empty())
            {
                if(i-dq.front()>=l)
                {
                    if(sp[i]-sp[dq.front()]>=0)
                        ok=1;
                }
            }
            while(!dq.empty())
            {
                if(sp[i]<=sp[dq.back()])
                    dq.pop_back();
                else
                    break;
            }
            dq.push_back(i);
        }

    if(ok)
    {
        ans=md;
        le=md+1;
    }
    else
        ri=md-1;
    }
    cout<<ans/100<<"."<<ans%100<<"\n";
    return 0;
}