Cod sursa(job #2274598)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 2 noiembrie 2018 10:04:10
Problema Secventa 3 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>

using namespace std;

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

int const nmax = 30000;
double const eps = 0.001;

#define MIN(a , b) (((a) < (b)) ? (a) : (b))
#define MAX(a , b) (((a) < (b)) ? (b) : (a))

int time[5 + nmax];
int cost[5 + nmax];
double v[5 + nmax];

double sum[5 + nmax];
double sol[5 + nmax];

bool test(double val  , int n , int l , int r){
  for(int i = 1 ; i <= n ; i++) {
    v[i] = time[i] - cost[i] * val;
  }

  for(int i = 1 ; i <= n ; i++) {
    sum[i] = sum[i - 1] + v[i];
  }


  int k = r - l + 1;

  deque<int> dqmin;

  for(int i = 1 ; i <= n ; i++){
    while(0 < dqmin.size() && sum[i] <= sum[dqmin.back()])
      dqmin.pop_back();

    dqmin.push_back(i);
    while(0 < dqmin.size() && dqmin.front() <= i - k)
      dqmin.pop_front();

    sol[i] = sum[dqmin.front()];
  }

  for(int i = 1 ; i <= n ; i++){
    if(l <= i) {
      if(sol[i - l] <= sum[i])
        return 1;
    }
  }
  return 0;
}

int main()
{
  int n , l , r;
  in >> n >> l >> r;
  for(int i = 1 ; i <= n ; i++)
    in >> time[i];
  for(int i = 1 ; i <= n ; i++)
    in >> cost[i];

  double x = 0;
  for(double jump = (1 << 20) ; eps < jump ; jump /= 2){
    if(test(x + jump , n , l , r) == 1)
      x += jump;
  }

  out << setprecision(2) << fixed << x;

  return 0;
}