Cod sursa(job #2217109)

Utilizator lucametehauDart Monkey lucametehau Data 29 iunie 2018 09:29:34
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <iomanip>
#include <deque>

using namespace std;

ifstream cin ("secv3.in");
ofstream cout ("secv3.out");

const double EPS = 1e-8;
const int VMAX = 1000;
const int NMAX = 30000;

int n, l, u;

double sum[1 + NMAX];
pair <double, double> v[1 + NMAX];
deque <int> dq;

bool Ok(double x) {
  int st = 1 - u, dr = 1 - l;
  for(int i = 1; i <= n; i++)
    sum[i] = sum[i - 1] + v[i].first - x * v[i].second;
  dq.clear();
  for(int i = 1; i <= n; i++, st++, dr++) {
    if(dr >= 0) {
      while(!dq.empty() && sum[dr] <= sum[dq.back()])
        dq.pop_back();
      dq.push_back(dr);
    }
    if(st >= 0) {
      while(!dq.empty() && dq.front() < st)
        dq.pop_front();
    }
    if(!dq.empty() && sum[i] >= sum[dq.front()])
      return 1;
  }
  return 0;
}

int main() {
  cin >> n >> l >> u;
  for(int i = 1; i <= n; i++)
    cin >> v[i].first;
  for(int i = 1; i <= n; i++)
    cin >> v[i].second;
  double st = 1e-3, dr = VMAX, mid, sol;
  for(int i = 1; i <= 30; i++) {
    mid = (st + dr) / 2;
    if(Ok(mid)) {
      sol = mid;
      st = mid;
    } else
      dr = mid;
  }
  cout << fixed << setprecision(2) << sol;
  return 0;
}