Cod sursa(job #2760572)

Utilizator cadmium_Voicu Mihai Valeriu cadmium_ Data 27 iunie 2021 22:52:43
Problema Secventa 3 Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <iomanip>  
#include <deque>

using namespace std;

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

int L,U,n;

double c[30000];
double s[30000];

double v[30002];

#define v (v+1)

deque<int> deq;
static void insert(int x) {
  while(!deq.empty() && deq.front()>v[x])
    deq.pop_front();
  deq.push_front(x);
}
static void pop(int x) {
  if(deq.back()==x)
    deq.pop_back();
}

static bool exists(double x) {
  deq=deque<int>();
  double temp;
  int i;
  //cout << x << ' '<< L-1 << '\n';
  for(i=0; i<n; i++) {
    v[i]=c[i]-s[i]*x+v[i-1];
    if(i>=L-1) {
      if(deq.empty())
        temp=0;
      else
        temp=v[deq.back()];
      //cout << v[i] <<' ' << temp << '\n';
      if(v[i]-temp>=0)
        return 1;
      insert(i-L+1);
      pop(i-U);
    }
  }
  return 0;
} 

int main() {
  int i;
  cin >> n>> L >> U;
  for(i=0; i<n; i++) {
    cin >> c[i];
  }
  for(i=0; i<n; i++)
    cin >> s[i];
  double mid,l=0,r=1000000000;
  while(r-l>=0.001) {
    mid=(l+r)/2;
    if(exists(mid))
      l=mid;
    else
      r=mid;
  }
  cout << setprecision(2) << fixed << l << '\n';
}