Cod sursa(job #1611171)

Utilizator RadduFMI Dinu Radu Raddu Data 23 februarie 2016 23:02:24
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");

deque <int> q;
int n,l,u,a[30005],b[30005],s[30005];
int Ans(int r)
{ int i,vmin,sol=-2147000000;
  for(i=1;i<=n;i++)
   {s[i]=s[i-1]+a[i]-b[i]*r;
  // cout<<s[i]<<"\n";
   }
   q.clear();
  for(i=1;i<=n;i++)
  {
     if (i-l>=1)
      { while(!q.empty() && s[i-l]<=s[q.back()]) q.pop_back();
        q.push_back(i-l);
      }

     if (i-u-1>=1)
      while(!q.empty() && q.back()<=i-u-1) q.pop_back();

    vmin=0;
     if (!q.empty() && s[q.back()]<vmin) vmin=s[q.back()];
    // cout<<i<<" "<<s[i]<<" "<<vmin<<"\n";
    sol=s[i]-vmin;
     if (sol>=0) return 1;
  }

  return 0;
}

void Search()
{ int st=0,dr=350000,mid;
   while(st<=dr)
   { mid=(st+dr)/2;
      if (Ans(mid)) st=mid+1; else dr=mid-1;
   }
   mid=(st+dr)/2;
   if (!Ans(mid)) mid--;

   g<<fixed<<setprecision(2)<<(double)mid/100<<"\n";
}
int main()
{ int i;
    f>>n>>l>>u;

    for(i=1;i<=n;i++)
     {f>>a[i];
      a[i]*=100;
     }
    for(i=1;i<=n;i++)
     f>>b[i];

   Search();
  return 0;
}