Pagini recente » Cod sursa (job #2627235) | Cod sursa (job #2729435) | Cod sursa (job #2379790) | Cod sursa (job #2493465) | Cod sursa (job #1068410)
#include<fstream>
#include<deque>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,L,U,cost[30100],timp[30100];
double v[30100],sum[30100];
deque <int> D;
inline bool Posibil(double X)
{
int i;
double best=-2000000000;
sum[0]=0.0;
for(i=1;i<=n;i++)
{
v[i]=1*cost[i]-1*timp[i]*X;
sum[i]=sum[i-1]+v[i];
}
D.clear();
for(i=L;i<=n;i++)
{
while(D.size() && sum[D.back()]>=sum[i-L])
D.pop_back();
D.push_back(i-L);
while(D.front()<i-U)
D.pop_front();
best=max(best,sum[i]-sum[D.front()]);
}
if(best>=0)
return true;
return false;
}
inline double CautareBinara()
{
double st,dr,mij,rez=0.0;
st=0.0;
dr=1000;
while(dr-st>0.001)
{
mij=(st+dr)/2;
if(Posibil(mij))
{
rez=mij;
st=mij;
}
else
dr=mij;
}
return rez;
}
int main()
{
int i;
ifstream fin("secv3.in");
fin>>n>>L>>U;
for(i=1;i<=n;i++)
fin>>cost[i];
for(i=1;i<=n;i++)
fin>>timp[i];
fin.close();
freopen("secv3.out","w",stdout);
printf("%.2lf\n",CautareBinara());
return 0;
}