Cod sursa(job #2607317)

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

  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] );

  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;
  }
  mij1 = mij2 = mij;

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

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

      if ( f == 0 )
        dr = mij1;
      else
        st = mij1;
    }
  }

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

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

      if ( f == 0 )
        dr = mij2;
      else
        st = mij2;
    }
  }

  if ( mij >= mij1 && mij >= mij2 )
    r = mij;
  else if ( mij1 >= mij && mij1 >= mij2 )
    r = mij1;
  else
    r = mij2;

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