Cod sursa(job #22267)

Utilizator stef2nStefan Istrate stef2n Data 25 februarie 2007 23:45:42
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <stdio.h>
#include <deque>
using namespace std;

#define infile "secv3.in"
#define outfile "secv3.out"
#define NMAX 30005
#define INF 1000000000000000.1

FILE *fin,*fout;
int N,L,U;
int c[NMAX],t[NMAX];
double suma[NMAX];
deque <int> D;

void citire()
  {
   int i;
   fin=fopen(infile,"r");
   fscanf(fin,"%d %d %d",&N,&L,&U);
   for(i=1;i<=N;i++)
      fscanf(fin,"%d",&c[i]);
   for(i=1;i<=N;i++)
      fscanf(fin,"%d",&t[i]);
   fclose(fin);
  }

void adauga_deque(int x)
  {
   while(!D.empty() && suma[D.back()]>=suma[x])
        D.pop_back();
   D.push_back(x);
  }

void elimina_deque(int x)
  {
   if(!D.empty() && D.front()==x)
     D.pop_front();
  }

inline double minim_deque()
  {
   return suma[D.front()];
  }

double sumamax(double X)
  {
   int i;
   double sol=-INF;
   suma[0]=0.;
   for(i=1;i<=N;i++)
      suma[i]=suma[i-1]+c[i]-X*t[i];
   D.clear();
   for(i=L;i<=N;i++)
      {
       elimina_deque(i-U-1);
       adauga_deque(i-L);
       if(sol<suma[i]-minim_deque())
         sol=suma[i]-minim_deque();
      }
   return sol;
  }

double solve(double li, double ls)
  {
   double mij=(li+ls)/2.;
   if(ls-li<0.001)
     return mij;
   double s=sumamax(mij);
   if(s<0)
     return solve(li,mij);
   else
     return solve(mij,ls);
  }


int main()
{
citire();
fout=fopen(outfile,"w");
fprintf(fout,"%lf\n",solve(0,1000));
fclose(fout);
return 0;
}