Cod sursa(job #133657)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 9 februarie 2008 13:38:05
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
//secventa3
#include<stdio.h>
#define maxn 30001
FILE*fin=fopen("secv3.in","r");
FILE*fout=fopen("secv3.out","w");
int cost[maxn],t[maxn],maxx=-1,ind[maxn];
double dec[maxn],sum[maxn];
int l,u,n,start,stop;
int mmx(double x)
{
  int st,dr,i,j;
  double 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(double xmin,double xmax)
{
  double mij;
  while(xmax-xmin>1e-3)
  {
    mij=(xmin+xmax)/2;
    if(mmx(mij)) xmin=mij;
    else xmax=mij;
  }
  fprintf(fout,"%.2f",xmin);
}
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);
  fclose(fout);
  return 0;
}