Cod sursa(job #3314765)

Utilizator hrib_the_slothAndreea Pasca hrib_the_sloth Data 11 octombrie 2025 03:32:42
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long i8;
vector<int> t(30005, 0);
vector<int> c(30005, 0);
int n, l, u;
bool _try(double x) {
  vector<double> pfx(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    pfx[i] = pfx[i - 1] + c[i] - x * t[i];
  }

  deque<int> d;
  double res = 0;
  for (int i = l; i <= n; i++) {
    while (!d.empty() && pfx[d.back()] >= pfx[i - l + 1]) {
      d.pop_back();
    }
    d.push_back(i - l);
    if (!d.empty()) {
      res = max(res, pfx[i] - pfx[d.front()]);
    }
    if (!d.empty() && d.front() < i - u) {
      d.pop_front();
    }
  }
  return res > 0;
}
int main() {
  ifstream cin("secv3.in");
  ofstream cout("secv3.out");
  cin >> n >> l >> u;

  for (int i = 1; i <= n; i++) {
    cin >> c[i];
  }

  for (int i = 1; i <= n; i++) {
    cin >> t[i];
  }

  double l = 0;
  double r = 1e9;

  while (r - l >= 0.0000000001) {
    double mid = (l + r) / 2;
    if (_try(mid)) {
      l = mid;
    } else {
      r = mid;
    }
  }
  cout << fixed << setprecision(2) << l << "\n";
  return 0;
}