Cod sursa(job #2213766)

Utilizator PetyAlexandru Peticaru Pety Data 17 iunie 2018 12:00:32
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("secv3.in");
ofstream fout ("secv3.out");

int n, a[30002], b[30002], l, u, st,dr;
double sol, sum[30002];

bool OareMerge (double val) {
  for (int i = 1; i <= n; i++) {
    sum[i] = (double)a[i] - b[i] * val + sum[i - 1];
  }
  deque<int>dq;
  for (int i = l; i <= n; i++) {
    while (!dq.empty() && sum[i - l] <= sum[dq.front()])
      dq.pop_front();
    dq.push_front(i - l);
    if (i >= u && !dq.empty() && dq.back() <= i - u)
      dq.pop_back();
    if (sum[i] - sum[dq.back()] >= 0)
      return true;
  }
  return false;
}

int main()
{
  fin >> n >> l >> u;
  for (int i = 1; i <= n; i++)
    fin >> a[i];
  for (int i = 1; i <= n; i++)
    fin >> b[i];
  st = 1; dr = 100000;
  while (st <= dr) {
    int mij = (st + dr) / 2;
    if (OareMerge((double)mij / 100)) {
      st = mij + 1;
      sol = (double)mij / 100;
    }
    else
      dr = mij - 1;
  }
  fout << fixed << setprecision(2) << sol;
  return 0;
}