Pagini recente » Diferente pentru runda/oji_go_11_12_2 intre reviziile 2 si 3 | Cod sursa (job #1329890) | Cod sursa (job #139733) | Cod sursa (job #1657005) | Cod sursa (job #1053376)
#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]*=100;
}
for(i=1;i<=n;i++)
scanf("%d",&t[i]);
p=0;
u=10000000;
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;
}