Cod sursa(job #1687525)

Utilizator lflorin29Florin Laiu lflorin29 Data 12 aprilie 2016 21:50:26
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAXN = 30007;

int N , L , U , A[MAXN] , B[MAXN] ;
double v[MAXN];

void citire()
{
  fin >> N>> L >> U;
  for(int i = 1 ; i <= N ; ++i)
    fin >> A[i];
  for(int i = 1; i<=N; ++i)
    fin >> B[i];
}

double Get()
{
  double s = 0;
  for(int i = 1 ; i<=N; ++i)
    s += 1.0 * A[i] / (1.0 * B[i]);
  return s;
}

void trans(double mij)
{
  for(int i = 1; i<=N; ++i) v[i] = A[i];
  for(int i=1;i<=N; ++i)
     v[i] -= mij * B[i];
  for(int i = 2 ; i <=N; ++i)
     v[i] += v[i-1];
}

void sterg(deque<pair<int, double>>&D, int k)
{
  while(!D.empty() && (k - D.front().first + 1 > U))
     D.pop_front();
}

bool grt(double a, double b)
{
  return a-b>0.001;
}

void add(int st, deque < pair<int, double>>&D)
{
  while(!D.empty() && D.back().second >= v[st - 1]) D.pop_back();
  D.push_back(make_pair(st, v[st - 1]));
}

bool ok(double mij)
{
  trans(mij);
  deque < pair<int, double>> D;
  int st = 1;
  add(st, D);
  for(int i = L ; i<=N; ++i)
  {
    if(i > L) st++, add(st, D);
    sterg(D , i);
    if(grt(v[i], D.front().second ))return 1;
  }
  return 0;
}

void solve()
{
  double st = 0 , dr = Get(), res = 0;
  cerr<<ok(1.25);
  for(int i = 0; i <= 30; ++i)
  {
    double m = (st+dr) / 2.0;
    if(ok(m) == 0) res = m , dr=m-1;
    else st=m+1;
  }
  fout<<fixed<<setprecision(2)<<res<<'\n';
}
int main()
{
  citire();
  solve();
}