Cod sursa(job #2099555)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 4 ianuarie 2018 15:03:34
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>

const int MAXN = 3e4;
const double EPS = 1e-3;

int c[MAXN], t[MAXN], dq[MAXN + 1];
double s[MAXN + 1];

bool check(double x, int l, int u, int n) {
  int b, e;
  s[0] = 0.0;
  for (int i = 1; i <= n; ++i) {
    s[i] = s[i - 1] + 1.0 * c[i - 1] - x * t[i - 1];
  }
  b = e = 0;
  for (int i = l; i <= n; ++i) {
    if (dq[b] + u == i - 1) {
      ++b;
    }
    while (b < e && s[dq[e - 1]] > s[i - l + 1]) {
      --e;
    }
    dq[e++] = i - l + 1;
    if (s[i] - s[dq[b]] > 0) {
      return 1;
    }
  }
  return 0;
}

int main() {
  int n, l, u;
  double x, i;
  FILE *f = fopen("secv3.in", "r");
  fscanf(f, "%d%d%d", &n, &l, &u);
  for (int i = 0; i < n; ++i) {
    fscanf(f, "%d", &c[i]);
  }
  for (int i = 0; i < n; ++i) {
    fscanf(f, "%d", &t[i]);
  }
  fclose(f);
  i = (1 << 9);
  for (x = 0.0; i > EPS; i /= 2.0) {
    if (check(i + x, l, u, n)) {
      x += i;
    }
  }
  f = fopen("secv3.out", "w");
  fprintf(f, "%.2lf\n", x);
  fclose(f);
  return 0;
}