Cod sursa(job #1687415)

Utilizator lflorin29Florin Laiu lflorin29 Data 12 aprilie 2016 20:52:52
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 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 i, int j)
{
  while(!D.empty() && (D.front().first < i || D.front().first > j)) D.pop_front();
}

bool grt(double a, double b)
{
  return a - b > 0.01;
}
bool ok(double mij)
{
  trans(mij);
  deque < pair<int, double>> D;
  for(int i = 1 ; i<=N; ++i)
  {
    while(!D.empty() && D.back().second >= v[i - 1]) D.pop_back();
        sterg(D, i - U + 1, i - L + 1);
    D.push_back(make_pair(i, v[i - 1]));
    sterg(D, i - U + 1, i - L + 1);
    if(!D.empty() && grt(v[i], D.front().second ))return 1;
  }
  return 0;
}

void solve()
{
  double st = 0 , dr = Get(), res = 0;
  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(4)<<res<<'\n';
}
int main()
{
  citire();
  solve();
}