Cod sursa(job #3366937)

Utilizator ultra980Alex Stan ultra980 Data 5 octombrie 2026 11:49:13
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <iomanip>
using namespace std;

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

using uint = unsigned int;

const int MAXNLU = 30'000;
const int MAXVAL = 1000;

struct FracSecv {
  // cost / timp
  // 
  int cost, timp;

  inline FracSecv operator +(const FracSecv &other) const {
    return {cost + other.cost, timp + other.timp};
  }

  inline FracSecv operator -(const FracSecv &other) const {
    return {cost - other.cost, timp - other.timp};
  }

  inline bool operator <(const FracSecv &o) const {
    return cost * o.timp < o.cost * timp;
  }

  inline bool operator ==(const FracSecv &o) const {
    return cost * o.timp == o.cost * timp;
  }

  inline FracSecv operator +=(const FracSecv &o) {
    cost += o.cost;
    timp += o.timp;
    return *this;
  }

  inline double crunch() const {
    return (double)cost / timp;
  }
} spart[MAXNLU + 1];

int n, l, u;

void citire() {
  int i;

  fin >> n >> l >> u;
  spart[0] = {0, 0};
  for (i = 1; i <= n; ++i) {
    fin >> spart[i].cost;
  }
  for (i = 1; i <= n; ++i) {
    fin >> spart[i].timp;
    spart[i] += spart[i - 1];
  }
}

double dif[MAXNLU + 1];

void calc_dif(double x) {
  int i;

  for (i = 1; i <= n; ++i) {
    dif[i] = spart[i].cost - x * spart[i].timp;
  }
}

bool exista_val_peste_x(double x) {
  int i, sp;
  deque<int> deq;

  calc_dif(x);

  sp = 0;
  
  for (i = l; i <= u; ++i) {
    while (!deq.empty() && dif[deq.back()] <= dif[i]) {
      deq.pop_back();
    }
    deq.push_back(i);
  }
  // printf("deq.front() = %d sp = %d dif[front] = %lf dif[sp] = %lf\n", deq.front(), sp, dif[deq.front()], dif[sp]);
  if (dif[deq.front()] >= dif[sp]) return true;
  // cout << "a trecut\n";

  for (sp = 1; sp + l <= n; ++sp) {
    if (deq.front() <= sp + l - 1) deq.pop_front();
    if (sp + u - 1 <= n) {
      while (!deq.empty() && dif[deq.back()] <= dif[sp + u - 1]) {
        deq.pop_back();
      }
      deq.push_back(sp + u - 1);
    }
    if (dif[deq.front()] >= dif[sp]) return true;
  }

  return false;
}

double cauta_x() {
  double lo = 0, hi = MAXVAL;
  double md;
  int i;

  for (i = 0; i < 30; ++i) {
    md = (lo + hi) / 2;
    // cout << "md = " << fixed << setprecision(3) << md << '\n';
    if (exista_val_peste_x(md)) {
      lo = md;
    } else {
      hi = md;
    }
  }
  return lo;
}

void afisare_x(double x) {
  fout << fixed << setprecision(3) << x << '\n';
}

int main() {
  citire();
  afisare_x(cauta_x());
}