Pagini recente » Cod sursa (job #2028145) | Profil M@2Te4i | Cod sursa (job #2481680) | Cod sursa (job #440879) | Cod sursa (job #1053379)
#include<cstdio>
#include<deque>
using namespace std;
int i,n,p,u,mij,lmin,lmax,ras,c[30009],t[30009],a[30009];
long long 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();}
long long Top(){return s[cc.front()];}
bool ok(int 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=1000000000;
while(p<=u)
{
mij=(p+u)>>1;
if(ok(mij))
{
ras=mij;
p=mij+1;
}
else u=mij-1;
}
ras/=10;
printf("%d.%d%d\n",ras/100,(ras%100)/10,(ras%100)%10);
return 0;
}