Cod sursa(job #2148795)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 1 martie 2018 23:48:29
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>
#include <deque>

using namespace std;

int a[30005], b[30005];
double s[30005];

int n, l, u;

bool ok(double val) {
  deque<int>d;
  for (int i = 1; i <= n; ++i) {
    double aux = (double)a[i] - val * b[i];
    s[i] = s[i - 1] + aux;
    if (i >= l) {
      while (!d.empty() && d.front() <= i - u)
        d.pop_front();
      while (!d.empty() && s[d.back()] >= s[i - l])
        d.pop_back();
      d.push_back(i - l);
      if (!d.empty() && s[d.front()] <= s[i])
        return 1;
    }
  }
  return 0;
}

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

  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]);
  int st = 1, dr = 100000, last;
  while (st <= dr) {
    int med = (st + dr) / 2;
    if (ok((double)med / 100))
      last = med, st = med + 1;
    else
      dr = med - 1;
  }

  printf("%.2f", (double)last / 100);

  return 0;
}