Cod sursa(job #2919471)

Utilizator AlexandruBenescuAlexandru Benescu AlexandruBenescu Data 17 august 2022 18:29:40
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <bits/stdc++.h>
#define INF 30000000
#define L 30005
#define LIM 40
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
int a[L], b[L], d[L], n, l, r;
double s[L];

inline double solve(double x){
  int i, st = 0, dr = -1;
  double mx = -INF;
  for (i = 1; i <= n; i++)
    s[i] = a[i] - x * b[i];
  for (i = l; i <= n; i++){
   if (st <= dr && d[st] == i - r - 1)
     st++;
   while (st <= dr && s[d[dr]] >= s[i - l])
     dr--;
    d[++dr] = i - l;
    mx = max(mx, s[i] - s[d[st]]);
  }
  return mx;
}

int main(){
  int i, x, limit;
  double le, ri, mid;
  fin >> n >> l >> r;
  for (i = 1; i <= n; i++){
    fin >> x;
    a[i] = a[i - 1] + x;
  }
  for (i = 1; i <= n; i++){
    fin >> x;
    b[i] = b[i - 1] + x;
  }
  le = 0;
  ri = INF;
  for (limit = 0; limit < LIM; limit++){
    mid = (le + ri) / 2;
    if (solve(mid) >= 0)
      le = mid;
    else
      ri = mid;
  }
  fout << setprecision(4) << le << "\n";
  return 0;
}