Pagini recente » Cod sursa (job #103743) | Cod sursa (job #1961464) | Cod sursa (job #1760235) | Cod sursa (job #1312263) | Cod sursa (job #206817)
Cod sursa(job #206817)
#include<stdio.h>
#define zero 0.0001
FILE *fin=fopen("secv3.in","r"),
*fout=fopen("secv3.out","w");
int U,L,N, c[30005],t[30005];
double a[300005];
int dq[300005];
int main(){
fscanf(fin,"%d%d%d",&N,&L,&U);
for(int i=1;i<=N;i++)
fscanf(fin,"%d",&c[i]);
for(int i=1;i<=N;i++)
fscanf(fin,"%d",&t[i]);
double li=0,lf=30000000;
while(lf-li>zero){
double mij=(li+lf)/2;
for(int i=1;i<=N;i++)
a[i]=(double)c[i]-mij*t[i]+a[i-1];
double sol=-30000000;
int lli=1,llf=0;
for(int i=L;i<=N;i++){
if(i-dq[lli]>=U)
++lli;
int j=i-L;
while(llf>=lli && a[j] < a[dq[llf]])
--llf;
dq[++llf]=j;
if(sol < a[i]-a[dq[lli]])
sol=a[i]-a[dq[lli]];
}
if(sol<zero)
lf=mij;
else
li=mij;
}
fprintf(fout,"%.2f",li);
fclose(fin);
fclose(fout);
return 0;
}