Cod sursa(job #1606947)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 20 februarie 2016 18:18:20
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 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;
    bool ok;
    long long ans,md,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(i>=l)
            {
            while(!dq.empty())
            {
                if(sp[i-l]<=sp[dq.back()])
                    dq.pop_back();
                else
                    break;
            }
            dq.push_back(i-l);
            if(sp[i]-sp[dq.front()]>=0)
                ok=1;
            }
        }

    if(ok)
    {
        ans=md;
        le=md+1;
    }
    else
        ri=md-1;
    }
    cout<<(double)ans/100;
    return 0;
}