Cod sursa(job #133419)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 8 februarie 2008 16:44:16
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
//secventa3
#include<stdio.h>
#define maxn 100
FILE*fin=fopen("secv3.in","r");
FILE*fout=fopen("secv3.out","w");
int sum[maxn],cost[maxn],t[maxn],maxx=-1,best,dec[maxn],ind[maxn];
int l,u,n,start,stop;
int mmx(int x)
{
  int st,dr,i,j;
  best=-1000;
  sum[0]=0;
  for(i=1;i<=n;i++)
      sum[i]=sum[i-1]+cost[i]-x*t[i];
  st=0;dr=0;dec[st]=0;ind[st]=0;
  if(sum[l]>best)
  {
    best=sum[l];
    start=1;stop=l;
  }
  for(i=l+1;i<=n;i++)
  {
    if(ind[st]<i-u) st++;
    j=dr;
    while(j>=st&&sum[i-l]<dec[j]) j--;
    dr=j+1;
    dec[dr]=sum[i-l];
    ind[dr]=i-l;
    if(sum[i]-dec[st]>best)
    {
      best=sum[i]-dec[st];
      start=ind[st]+1;
      stop=i;
    }
  }
  if(best>0) return 1;
  return 0;
}
void cb(int xmin,int xmax)
{
  int mij;
  if(xmin==xmax) if(mmx(xmin)) return ;
		 else{mmx(xmin-1);return ;}
  else
  {
    mij=(xmin+xmax)>>1;
    if(mmx(mij))
      cb(mij+1,xmax);
    else
      cb(xmin,mij-1);
  }
}
int main()
{
  double n1=0,n2=0;
  int i;
  fscanf(fin,"%d%d%d",&n,&l,&u);
  for(i=1;i<=n;i++)
  {
    fscanf(fin,"%d",&cost[i]);
    if(maxx<cost[i]) maxx=cost[i];
  }
  for(i=1;i<=n;i++)
    fscanf(fin,"%d",&t[i]);
  fclose(fin);
  cb(0,maxx);
  for(i=start;i<=stop;i++)
  {
    n1+=cost[i];
    n2+=t[i];
  }
  fprintf(fout,"%.2lf",(n1/n2));
  fclose(fout);
  return 0;
}