Pagini recente » Cod sursa (job #933930) | Cod sursa (job #1394700) | Cod sursa (job #1039092) | Cod sursa (job #1286364) | Cod sursa (job #70517)
Cod sursa(job #70517)
#include<stdio.h>
int n,l,h;
int c[30003],t[30003];
double b[30003];
double deque(double x)
{
//b[i]=c[i]-x*t[i]
int i,j;
double r=1050.0;
b[0]=0;
for(i=1;i<=n;i++)
{
b[i]=(double)c[i]-x*(double)t[i];
b[i]+=b[i-1];
}
int dq[30003],li,lf;
li=1;lf=0;
/*
for(i=1;i<=n;i++)
{
if(li<=lf)
if(dq[li]<i-h)
li++;
if(i-l>=0)
{
while(lf>=li&&b[i-l]<b[dq[lf]]) lf--;
dq[++lf]=i-l;
}
if(li<=lf)
if(b[i]-b[dq[li]]>r||r==1050)
r=b[i]-b[dq[li]];
}
*/
li=lf=1;
dq[1]=0;
for(i=l;i<=n;i++)
{
if(b[i]- b[dq[li]] > r || r==1050.0)
r= b[i]- b[dq[li]];
if(i-dq[li] == h) li++;
j=i-l+1;
while(li<=lf && b[dq[lf]] > b[j] ) lf--;
dq[++lf]= j;
}
return r;
}
int main()
{
FILE *fin=fopen("secv3.in","r"),*fout=fopen("secv3.out","w");
fscanf(fin,"%d%d%d",&n,&l,&h);
int i;
for(i=1;i<=n;i++)
fscanf(fin,"%d",&c[i]);
for(i=1;i<=n;i++)
fscanf(fin,"%d",&t[i]);
double li,lf,m,biggest;
li=0;lf=1005;
while(lf-li>0.0001)
{
m=(li+lf)/2;
biggest=deque(m);
if(biggest>0)
li=m;
else
lf=m;
}
//fprintf(fout,"%f\n",lf);
int aux;
aux=(int)li;
fprintf(fout,"%d.",aux);
li-=aux;
li*=100;
aux=(int) li;
fprintf(fout,"%02d\n",aux);
fclose(fin);
fclose(fout);
return 0;
}