Cod sursa(job #2607367)

Utilizator alex_benescuAlex Ben alex_benescu Data 29 aprilie 2020 17:28:04
Problema Secventa 3 Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <stdio.h>
#define NMAX 30003
#define EPS 0.001
#define MAXVAL 33554432
#define TEN 1000
using namespace std;
int vcost[NMAX], vtimp[NMAX];
float v[TEN + 3];
int main() {
  freopen ( "secv3.in", "r", stdin );
  freopen ( "secv3.out", "w", stdout );
  int n, lmin, lmax, i, scost, stimp, f, k;
  float dr, st, mij;

  scanf ( "%d%d%d", &n, &lmin, &lmax );
  for ( i = 0; i < n; i ++ )
    scanf ( "%d", &vcost[i] );
  for ( i = 0; i < n; i ++ )
    scanf ( "%d", &vtimp[i] );

  if ( lmax - lmin > TEN ) {
    st = 0;
    dr = MAXVAL;
    while ( dr - st > EPS ) {
      mij = (float) ( dr + st ) / 2;
      scost = stimp = 0;

      for ( i = 0; i < lmin; i ++ ) {
        scost += vcost[i];
        stimp += vtimp[i];
      }
      if ( (float) scost / stimp < mij )
        f = 0;
      else
        f = 1;
      for ( i = lmin; i < n; i ++ ){
        scost = scost - vcost[i - lmin] + vcost[i];
        stimp = stimp - vtimp[i - lmin] + vtimp[i];
        if ( (float) scost / stimp > mij )
          f = 1;
      }

      if ( f == 0 )
        dr = mij;
      else
        st = mij;
    }
  }
  else {
    for ( k = lmin; k <= lmax; k ++ ) {
      st = 0;
      dr = MAXVAL;
      while ( dr - st > EPS ) {
        mij = (float) ( dr + st ) / 2;
        scost = stimp = 0;

        for ( i = 0; i < k; i ++ ) {
          scost += vcost[i];
          stimp += vtimp[i];
        }
        if ( (float) scost / stimp < mij )
          f = 0;
        else
          f = 1;
        for ( i = k; i < n; i ++ ){
          scost = scost - vcost[i - k] + vcost[i];
          stimp = stimp - vtimp[i - k] + vtimp[i];
          if ( (float) scost / stimp > mij )
            f = 1;
        }

        if ( f == 0 )
          dr = mij;
        else
          st = mij;
      }
      v[k - lmin] = mij;
    }

    mij = v[0];
    for ( i = 1; i < TEN + 3; i ++ )
      if ( mij < v[i] )
        v[i] = mij;
  }

  printf ( "%f\n", mij );
  return 0;
}