Cod sursa(job #70517)

Utilizator moga_florianFlorian MOGA moga_florian Data 6 iulie 2007 11:35:19
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#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;   
}