Cod sursa(job #1053373)

Utilizator geniucosOncescu Costin geniucos Data 12 decembrie 2013 18:34:25
Problema Secventa 3 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<cstdio>
#include<deque>
using namespace std;
int i,n,p,u,mij,lmin,lmax,ras,c[30009],t[30009],a[30009],s[30009];
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();}
int Top(){return s[cc.front()];}
bool ok(int cost)
{
    for(i=1;i<=n;i++)
    {
        a[i]=c[i]-t[i]*cost;
        s[i]=s[i-1]+a[i];
    }
    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]*=100;
}
for(i=1;i<=n;i++)
    scanf("%d",&t[i]);
p=0;
u=1000000;
while(p<=u)
{
    mij=(p+u)>>1;
    if(ok(mij))
    {
        ras=mij;
        p=mij+1;
    }
    else u=mij-1;
}
printf("%d.%d%d\n",ras/100,(ras%100)/10,(ras%100)%10);
return 0;
}