Pagini recente » Cod sursa (job #36942) | Cod sursa (job #2148119) | Cod sursa (job #2461525) | Cod sursa (job #917094) | Cod sursa (job #1728810)
#include <cstdio>
#include <cstring>
#define MAXN 30000
double cost[MAXN+1],timp[MAXN+1],v[MAXN+1];
int deq[MAXN+1];
int n,l,u;
inline char cauta(double medie){
int i,b,e;
double max=-1000000000;
for(i=1;i<=n;i++){
v[i]=cost[i]-medie*timp[i];
v[i]+=v[i-1];
}
memset(deq,0,sizeof(deq));
b=0;
e=-1;
for(i=1;i<=n;i++){
if(deq[b]<i-u)
b++;
if(i-l>=0){
while(e>=b&&v[i-l]<=v[deq[e]])
e--;
deq[++e]=i-l;
}
if(v[i]-v[deq[b]]>max)
max=v[i]-v[deq[b]];
}
return (max>0);
}
int main(){
FILE*fi,*fout;
int i;
double rez,pas,EPS;
fi=fopen("secv3.in" ,"r");
fout=fopen("secv3.out" ,"w");
fscanf(fi,"%d%d%d" ,&n,&l,&u);
EPS=0.0000001;
for(i=1;i<=n;i++)
fscanf(fi,"%lf" ,&cost[i]);
for(i=1;i<=n;i++)
fscanf(fi,"%lf" ,&timp[i]);
pas=1;
for(i=1;i<=12;i++)
pas*=2;
rez=0;
for(;pas>EPS;pas/=2)
if(cauta(rez+pas)==1)
rez+=pas;
fprintf(fout,"%lf" ,rez);
fclose(fi);
fclose(fout);
return 0;
}