Cod sursa(job #838439)

Utilizator stoicatheoFlirk Navok stoicatheo Data 19 decembrie 2012 18:15:33
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<cstdio>
#include<cmath>
#include<deque>
#include<algorithm>
using std::max;
using std::deque;
 
long long t[30005];
long long c[30005];
long long v[30005];
int n,l,u;
 
bool isok (long long m)
{   
    for(int i=0;i<n;i++)
        v[i]=v[i-1]+c[i]*100-t[i]*m;
 
    deque<long long> d;
    if(v[l]>=0)
        return true;
    else{
        for(int i=l;i<n;i++){
            while(d.empty()==false&&v[d.back()]>v[i-l])
                d.pop_back();
            d.push_back (i-l);
            while(d.front()<=i-u-1)
                d.pop_front();
            if(v[i]-v[d.front()]>=0){
                return true;
            }
        }
    }
    return false;
}
 
int main()
{
    freopen ("secv3.in","r",stdin);
    freopen ("secv3.out","w",stdout);
 
    scanf ("%d%d%d",&n,&l,&u);
 
    scanf ("%lld",c);
    for(int i=1;i<n;i++)
        scanf ("%lld",c+i);
 
    scanf ("%lld",t);
    for(int i=1;i<n;i++)
        scanf ("%lld",t+i);
 
    long long s=1,e=200000000005;
 
    while(s<e){
        long long m=(s+e)/2;
        if(m==s)
            m=e;
 
        if(isok (m))
            s=m;
        else
            e=m-1;
    }
    printf ("%lld.%02lld",s/100,s%100);
    return 0;
}