Pagini recente » Cod sursa (job #1088044) | Cod sursa (job #532025) | Cod sursa (job #1591625) | Cod sursa (job #1648769) | Cod sursa (job #638714)
Cod sursa(job #638714)
#include <fstream>
using namespace std;
const int N=30005;
const double E=1e-3;
int a[N],b[N],dq[N],n,L,U,st,dr;
double val[N];
ifstream in("secv3.in");
ofstream out("secv3.out");
inline void pop(int x)
{
if (dq[st]==x)
st++;
}
void push(int x)
{
while (st<=dr && val[dq[dr]]>=val[x])
dr--;
dq[++dr]=x;
}
bool ok(double x)
{
int i;
st=1,dr=0;
for (i=1;i<=n;i++)
val[i]=val[i-1]+a[i]-b[i]*x;
for (i=L;i<=n;i++)
{
pop(i-U-1);
push(i-L);
if (val[dq[st]]<=val[i])
return true;
}
return false;
}
double bs()
{
double i,step=512;
for (i=0;E<=step;step/=2)
if (ok(i+step))
i+=step;
return (double)((int)(i*100))/100;
}
int main()
{
in>>n>>L>>U;
for (int i=1;i<=n;i++)
in>>a[i];
for (int i=1;i<=n;i++)
in>>b[i];
out<<bs()<<"\n";
return 0;
}