Cod sursa(job #27607)

Utilizator stef2nStefan Istrate stef2n Data 6 martie 2007 20:39:03
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <stdio.h>
#include <deque>
using namespace std;

#define infile "buline.in"
#define outfile "buline.out"
#define INF 2000000005
#define NMAX 200005

FILE *fin,*fout;
int n,X[2*NMAX];
int sumamax=-INF,pozmin,L;
deque<int> D;
int S[2*NMAX];

void citire()
  {
   int i,cul;
   fin=fopen(infile,"r");
   fscanf(fin,"%d",&n);
   X[0]=0;
   for(i=1;i<=n;i++)
      {
       fscanf(fin,"%d %d",&X[i],&cul);
       if(!cul)
         X[i]=-X[i];
      }
   for(i=n+1;i<=2*n;i++)
      X[i]=X[i-n];
   fclose(fin);
  }

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

inline void sterge_deque(int x)
  {
   if(D.empty())
     return;
   if(D.front()==x)
     D.pop_front();
  }

inline int min_deque()
  {
   return D.front();
  }

void solve()
  {
   int i,poz,change;
   S[0]=0;
   adauga_deque(0);
   for(i=1;i<=2*n;i++)
      {
       S[i]=S[i-1]+X[i];
       sterge_deque(i-n-1);

       poz=min_deque();
       change=0;
       if(sumamax<S[i]-S[poz])
         change=1;
       else
         if(sumamax==S[i]-S[poz])
           if(poz<pozmin)
             change=1;
           else
             if(poz==pozmin && L>i-poz)
               change=1;
       if(change)
         {
          sumamax=S[i]-S[poz];
          pozmin=poz;
          L=i-poz;
         }

       adauga_deque(i);
      }
  }

int main()
{
citire();
solve();
fout=fopen(outfile,"w");
fprintf(fout,"%d %d %d\n",sumamax,pozmin+1,L);
fclose(fout);
return 0;
}