Pagini recente » Cod sursa (job #27584) | Rating Burghelea Andi Gabriel (Don_Genove) | Cod sursa (job #2380057) | Cod sursa (job #1828887) | Cod sursa (job #1053395)
#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;
}
printf("%lld.%lld%lld%lld\n",ras/1000,(ras%1000)/100,((ras%1000)/10)%10,(ras%1000)%10);
return 0;
}