Cod sursa(job #113700)

Utilizator mgntMarius B mgnt Data 11 decembrie 2007 10:54:40
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

int const maxlen = 30000;
int const maxval  = 1000;
int const minval  = 1;

double  sum[maxlen];
double maxs[maxlen];
   int   len[maxlen];

double findmax(double *z, int n, int minl, int maxl) {
  double  val;
  int i;

  sum[0]=z[0];
  for(i=1;i<n;i++) sum[i]=sum[-1+i]+z[i];
  for(i=-1+n; i>=-1+minl; i--) sum[i]-=sum[i+1-minl];

  maxl=maxl-minl+1;
  maxs[0]=z[0];
   len[0]=1;
  for(i=1;i<n;i++) {
    val=maxs[-1+i];
    if(maxl == len[-1+i]) {
      val-=z[-1+i-maxl+1];
      if(0<val) {
        maxs[i]=val+z[i];
         len[i]=len[-1+i];
      } else {
        maxs[i]=z[i];
         len[i]=1;
      }
    } else {
      if(0<val) {
        maxs[i]=val+z[i];
         len[i]=1+len[-1+i];
      } else {
        maxs[i]=z[i];
         len[i]=1;
      }
    }
  } // for

  val=-1;
  for(i=-1+minl;i<n;i++) {
    sum[i]=sum[i]+maxs[i+1-minl];
    if(val<sum[i]) val=sum[i];
  }
  return val;
}

int main()
{
  FILE * fin, * fout;
  int x[maxlen], y[maxlen];
  double zx[maxlen], zy[maxlen], z[maxlen];
  int n, minl, maxl, i;
  double a, b, c, v;

  fin = fopen("secv3.in", "r");
  setvbuf(fin, NULL, _IOFBF, 100 * 1024);
  fscanf(fin, "%d %d %d", &n, &minl, &maxl);
  for(i=0;i+10<n;i+=10)
    fscanf(fin, "%d %d %d %d %d %d %d %d %d %d",
      &x [0+i], &x [1+i], &x[2+i], &x[3+i], &x[4+i],
      &x [5+i], &x [6+i], &x[7+i], &x[8+i], &x[9+i]);
  for( ;i<n;i++)
    fscanf(fin, "%d", &x[i]);
  for(i=0;i+10<n;i+=10)
    fscanf(fin, "%d %d %d %d %d %d %d %d %d %d",
      &y [0+i], &y [1+i], &y[2+i], &y[3+i], &y[4+i],
      &y [5+i], &y [6+i], &y[7+i], &y[8+i], &y[9+i]);
  for( ;i<n;i++)
    fscanf(fin, "%d", &y[i]);
  fclose(fin);

  for(i=0;i<n;i++) { zx[i]=x[i]; zy[i]=y[i]; }

  a= ((double) minval) / ((double)maxval);
  b= ((double) maxval) / ((double)minval);
  while(b-a>10e-4) {
    c=(a+b)/2;
    for(i=0;i<n;i++) z[i]=zx[i]-c*zy[i];
    v = findmax(z, n, minl, maxl);
    if(fabs(v)<10e-10) {
      a = b = c;
    } else if(0<v) {
      a = c;
    } else {
      b = c;
    }
  }
  fout=fopen("secv3.out", "w");
  fprintf(fout, "%.2lf\n", a);
  fclose(fout);
  return 0;
}

/*
 x1+...+xk
 ---------  = z
 y1+...+yk

 (x1-zy1)+...+(xk-zyk)
--------------------- = 0
     y1+...+yk


 x1+...+xk    max+...+max      k max
 --------- <= ------------ <= ------ = max/min
 y1+...+yk     y1+...+yk       k min

 x1+..+xk        k min
 --------   <= --------
 y1+...+yk       k max

*/