Cod sursa(job #1053383)

Utilizator geniucosOncescu Costin geniucos Data 12 decembrie 2013 18:41:20
Problema Secventa 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<cstdio>
#include<deque>
using namespace std;
int i,n,lmin,lmax,c[30009],t[30009],a[30009];
long long s[30009],p,u,mij,ras;
deque < int > cc;
void Insert(int i){while(!cc.empty()&&s[cc.back()]>=s[i]) cc.pop_back();cc.push_back(i);}
void Erase(int i){while(!cc.empty()&&cc.front()>=i) cc.pop_front();}
long long Top(){return s[cc.front()];}
bool ok(long long cost)
{
    for(i=1;i<=n;i++)
        s[i]=s[i-1]+c[i]-1LL*t[i]*cost;
    while(!cc.empty()) cc.pop_front();
    for(i=lmin;i<=n;i++)
    {
        Insert(i-lmin);
        if(s[i]-Top()>=0) return 1;
        if(i>=lmax) Erase(i-lmax);
    }
    return 0;
}
int main()
{
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
scanf("%d",&n);
scanf("%d",&lmin);
scanf("%d",&lmax);
for(i=1;i<=n;i++)
{
    scanf("%d",&c[i]);
    c[i]*=1000;
}
for(i=1;i<=n;i++)
    scanf("%d",&t[i]);
p=0;
u=300000000000;
while(p<=u)
{
    mij=(p+u)>>1;
    if(ok(mij))
    {
        ras=mij;
        p=mij+1;
    }
    else u=mij-1;
}
ras/=10;
printf("%lld.%lld%lld\n",ras/100,(ras%100)/10,(ras%100)%10);
return 0;
}