Cod sursa(job #1588671)

Utilizator DjokValeriu Motroi Djok Data 3 februarie 2016 14:30:03
Problema Secventa 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<bits/stdc++.h>
using namespace std;

int i,n,u,l,a[30005],b[30005],deq[30005];
double st,dr=1000,pivot,rs,aux[30005];

bool Check(float x) {
    int st=1,dr=0,i;

    for(i=1;i<=n;++i) aux[i]=aux[i-1]+a[i]-x*b[i];

    for(i=l;i<=n;++i)
    {
      while(st<=dr && aux[deq[dr]]>=aux[i]) --dr;
      if(deq[st]<i-u) ++st;
      deq[++dr]=i-l;
      if(aux[i]>=aux[deq[st]]) return 1;
    }

    return 0;
}

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

  ios_base::sync_with_stdio(0); cin.tie(0);

  cin>>n>>l>>u;
  for(i=1;i<=n;++i) cin>>a[i];
  for(i=1;i<=n;++i) cin>>b[i];

  while(st<=dr)
  {
    pivot=(st+dr)/2.0;
    if(Check(pivot)) rs=pivot,st=pivot+0.001;
    else dr=pivot-0.001;
  }

  cout<<setprecision(2)<<fixed<<rs<<'\n';

 return 0;
}