Mai intai trebuie sa te autentifici.

Cod sursa(job #604828)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 25 iulie 2011 15:52:57
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>

const int N = 30010;

int n, l, u, a[N], b[N], dq[N];

int st, dr;

double s[N];

const double eps = 0.01;

void read() {
  scanf("%d%d%d", &n, &l, &u);

  for (int i = 1; i <= n; ++ i)
    scanf("%d", &a[i]);

  for (int i = 1; i <= n; ++ i)
    scanf("%d", &b[i]);
}

void elimst(int poz) {
  if (st <= dr && dq[st] == poz - u)
    ++ st;
}

void elimdr(int poz) {
  while (dr >= st && s[poz - l] < s[dq[dr]])
    -- dr;
}

bool verif(double val) {
  st = 1, dr = 0;

  for (int i = 1; i <= n; ++ i)
    s[i] = (double)s[i - 1] + (double)a[i] - val * (double)b[i];

  for (int i = l; i <= n; ++ i) {
    elimst(i);

    elimdr(i);

    dq[++ dr] = i - l;
  
    if (s[i] - s[dq[st]] > - eps)
      return 1;
  }

  return 0;
}

double cautb() {
  double mij, sol = 0, s = 0, d = (1 << 30);

  while (s + eps < d) {
    mij = (s + d) * 0.5;

    if (verif(mij)) {
      sol = mij;
      s = mij;
    } else
      d = mij;
  }

  return sol;
}

int main() {
  freopen("secv3.in", "r", stdin);
  freopen("secv3.out", "w", stdout);
  
  read();

  printf("%.2lf", cautb());

  return 0;
}