Pagini recente » Cod sursa (job #1341384) | Cod sursa (job #2051085) | Monitorul de evaluare | Cod sursa (job #294782) | Cod sursa (job #384189)
Cod sursa(job #384189)
#include<stdio.h>
#define infile "secv3.in"
#define outfile "secv3.out"
#define nmax 31313
#define vmax 1000
int a[nmax]; //secventa cu costurile
int b[nmax]; //secventa cu timpii
int n; //lungimea secventelor
int l,u; //lungimea minima, respectiv lungimea maxima a subsecventelor
double med; //media maxima
void read()
{
int i;
scanf("%d %d %d\n",&n,&l,&u);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
for(i=1;i<=n;i++) scanf("%d",&b[i]);
}
int verif(double med)
{ //trebuie sa verificam daca se poate obtine aceasta medie
double c[n+1]; //c[i]=a[1]-med*b[1] + a[i]-med*b[i]
double d[n+1]; //d[i]=suma unei subsecvente de lungime cel mult (u-l+2) din c[] ce se termina pe pozitia i
int e[n+1],st,dr; //deq
int i;
//il construim pe c
for(c[0]=0,i=1;i<=n;i++)
c[i]=c[i-1]+(double)a[i]-(med*b[i]);
//facem deq-ul
for(st=1,dr=0,i=1;i<=n;i++)
{
while(st<=dr && c[e[dr]]>=c[i]) dr--;
e[++dr]=i;
while(st<=dr && i-e[st] > u-l) st++;
d[i]=c[i]-c[e[st]];
}
//acum trebuie sa verificam daca exista o secventa cu suma pozitiva
for(i=l;i<=n;i++)
if(c[i]-c[i-l]+d[i-l] >= 0)
return 1;
//daca am ajuns aici, inseamna ca toate subsecventele sun negative
return 0;
}
void solve()
{
double mij,st=0,dr=vmax;
while(st<=dr)
{ //cautam binar media
mij=(st+dr)/2;
if(verif(mij)) med=mij,st=mij+0.000001;
else dr=mij-0.000001;
}
}
void write()
{
printf("%lf\n",med);
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
read();
solve();
write();
fclose(stdin);
fclose(stdout);
return 0;
}