Cod sursa(job #3316439)

Utilizator RaresHRares Hanganu RaresH Data 18 octombrie 2025 19:22:36
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <stdio.h>
#include <deque>
#include <math.h>

FILE* fin;
FILE* fout;

const int MAX_N = 30'000;
const double EPS = 1e-3;
const int MAX_C = 1'000;

int n, l, r;
int c[MAX_N + 1], t[MAX_N + 1];

double get_value(int idx, double mid) {
  return c[idx] - mid * t[idx];
}

bool check(double mid) {
  std::deque<double> dq;
  for(int i = l; i <= n; i++) {
    if(!dq.empty() && i - r >= 0 &&
       abs(dq.front() - get_value(i - r, mid)) < EPS) {
      dq.pop_front();
    }

    double x = get_value(i - l, mid);
    while(!dq.empty() && dq.back() > x) {
      dq.pop_back();
    }
    dq.push_back(x);

    double val = get_value(i, mid);
    if(dq.front() <= val) {
      return true;
    }
  }
  return false;
}

int main() {
  fin = fopen("secv3.in", "r");
  fout = fopen("secv3.out", "w");

  fscanf(fin, "%d%d%d", &n, &l, &r);

  for(int i = 1; i <= n; i++) {
    fscanf(fin, "%d", &c[i]);
    c[i] += c[i - 1];
  }
  for(int i = 1; i <= n; i++) {
    fscanf(fin, "%d", &t[i]);
    t[i] += t[i - 1];
  }

  double st = 0;
  double dr = MAX_C + EPS;
  while(dr - st > EPS) {
    double mij = (st + dr) / 2;
    if(check(mij)) {
      st = mij;
    } else {
      dr = mij;
    }
  }

  fprintf(fout, "%.2lf\n", st);

  fclose(fin);
  fclose(fout);

  return 0;
}