Cod sursa(job #1611314)

Utilizator RadduFMI Dinu Radu Raddu Data 24 februarie 2016 00:30:07
Problema Secventa 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#define fact 10000
#define ll long long
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");

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

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


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

  return 0;
}

void Search()
{ int st=0,dr=30005*fact,mid;
   while(st<=dr)
   { mid=(st+dr)/2;
      if (Ans(mid)) st=mid+1; else dr=mid-1;
    //cout<<mid<<" "<<Ans(mid)<<"\n";
   }
   mid=(st+dr)/2;
   if (!Ans(mid)) mid--;

   Ans(mid);

  // g<<fixed<<setprecision(4)<<(double)mid/fact<<"\n";
}
int main()
{ int i,j,t; double sol=0,s1,s2,r1=0,r2=0;
    f>>n>>l>>u;
    srand(time(NULL));
    i=rand()+rand()-rand();

    for(i=1;i<=n;i++)
     {f>>a[i];
    // a[i]=(rand()%1000)+1;
      a[i]*=fact;
     }

    for(i=1;i<=n;i++)
     { f>>b[i];
        // b[i]=(rand()%1000)+1;

     }

   /* for(i=1;i<=n;i++)
     for(j=i+l-1;j<=i+u-1;j++)
    if (j<=n)
    { s1=0; s2=0;
       for(t=i;t<=j;t++)
       { s1+=a[t]; s2+=b[t]; }

      if ((double) s1/s2>(double) sol) {sol=(double) s1/s2; mxi=i; mxj=j;}
    }
 */
   Search();
 for(i=mxi+1;i<=mxj;i++)
 { r1+=a[i]; r2+=b[i];}
 cout<<r1<<" "<<r2<<"\n";
 g<<fixed<<setprecision(9)<<(double) (r1/fact)/r2;
 //g<<fixed<<setprecision(4)<<(double) sol/fact<<"\n";
  /*for(i=1;i<=n;i++)
   g<<a[i]/100<<" ";
   g<<"\n";
  for(i=1;i<=n;i++)
   g<<b[i]<<" ";
 g<<"\n"<<mxi<<" "<<mxj;
*/
  return 0;
}