Pagini recente » Cod sursa (job #990485) | Cod sursa (job #1492309) | Cod sursa (job #2903201) | Cod sursa (job #981859) | Cod sursa (job #379689)
Cod sursa(job #379689)
#include <stdio.h>
#include <string.h>
#define NMAX 30001
#define LIM 0.001
int n,l,u,A[NMAX],B[NMAX],inc,sf,deq[NMAX];
double val=(1<<15),C[NMAX],sum[NMAX],rez;
void read()
{
scanf("%d%d%d",&n,&l,&u);
int i;
for (i=1; i<=n; i++)
scanf("%d",&A[i]);
for (i=1; i<=n; i++)
scanf("%d",&B[i]);
}
void capat(int i)
{
if (i-deq[inc]>l+1)
inc++;
}
void actualizare(int i)
{
while (inc!=sf && sum[i]<=sum[deq[sf-1]])
--sf;
deq[sf++]=i;
}
inline int ok(double x)
{
int i;
inc=0;sf=0;
for (i=1; i<=n; i++)
C[i]=(double)A[i]-(double)B[i]*x;
memset(deq,0,sizeof(deq));
for (i=1; i<=n; i++)
{
sum[i]=sum[i-1]+C[i];
if (i>=l && sum[i]-sum[deq[inc]]>=0)
return 1;
if (i>=l)
{
actualizare(i-l+1);
capat(i-l+1);
}
}
return 0;
}
void cbin()
{
while (val>LIM)
{
if (ok(rez+val))
rez+=val;
val/=2;
}
}
int main()
{
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
read();
cbin();
printf("%.2lf\n",rez);
return 0;
}