Cod sursa(job #22172)

Utilizator stef2nStefan Istrate stef2n Data 25 februarie 2007 21:40:19
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <stdio.h>
#include <deque>
using namespace std;

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

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

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

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

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

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

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

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


int main()
{
int val;
citire();
val=solve(0,1000000);
fout=fopen(outfile,"w");
fprintf(fout,"%d.%d%d\n",val/1000,(val%1000)/100,(val%100)/10);
fclose(fout);
return 0;
}