Pagini recente » Cod sursa (job #749302) | Cod sursa (job #208313) | Cod sursa (job #1999703) | Cod sursa (job #2011560) | Cod sursa (job #458099)
Cod sursa(job #458099)
#include <cstdio>
#define file_in "secv3.in"
#define file_out "secv3.out"
#define nmax 30100
int n,l,U;
double c[nmax];
double t[nmax];
double suma[nmax];
double b[nmax];
int d[nmax];
void citire()
{
int i;
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d %d %d", &n,&l,&U);
for (i=1;i<=n;++i)
scanf("%lf", &c[i]);
for (i=1;i<=n;++i)
scanf("%lf", &t[i]);
}
double secv(double X)
{
int i,sol;
for (i=1;i<=n;++i)
b[i]=c[i]-t[i]*X;
suma[0]=0;
//calculeaza suma pana la l
for (i=1;i<=l;++i) suma[0]+=b[i];
int p,u;
p=0;
u=0;
double q=0,max=suma[0];
double x=suma[0];
d[p]=1;
for (i=l+1;i<=n;++i)
{
q+=b[i];
x-=b[i-l];
while(p<=u && i-d[p]>=U) p++;
while(p<=u && suma[u]<x) u--;
suma[++u]=x;
d[u]=i-l+1;
if (p<=u && suma[p]+q>max)
max=q+suma[p];
}
return max;
}
double abs(double x) { return x>=0?x:-x; }
double brute()
{
int nr,i,j;
double max=0.0;
double suma1,suma2;
for (i=1;i<=n;++i)
{
suma1=c[i];
suma2=t[i];
nr=1;
if (nr>=l && nr<=U && suma1/suma2>max)
max=suma1/suma2;
for (j=i+1;j<=n;++j)
{
suma1+=c[j];
suma2+=t[j];
nr++;
if (nr>=l && nr<=U && suma1/suma2>max)
max=suma1/suma2;
if (nr>U) break;
}
}
return max;
}
void solve()
{
double ls,ld;
double mij;
double sol=0.0;
ls=0;
ld=10000;
while(ls<=ld)
{
mij=(double)((ls+ld)/2);
double x=(secv(mij));
if (x-sol>0.01)
{
sol=x;
ls=mij+1;
}
else
ld=mij-1;
}
printf("%.2lf\n", sol);
}
int main()
{
citire();
if (n<=1000)
printf("%.2lf\n", brute());
else
solve();
fclose(stdin);
fclose(stdout);
return 0;
}