Cod sursa(job #27671)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 6 martie 2007 22:27:58
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<stdio.h>
#include<iostream.h>
#define MAXN 400001
#define INF 2000000002
 long pA,pB,N,U,L;
 long V[MAXN];
 long poz[MAXN],query[MAXN];
 long REZ, X[MAXN],m;
 long deque[MAXN];

void citesteDate()
{
 int i;
 freopen("buline.in","r",stdin);
 scanf("%d",&N);L=1;U=N;
 //cout<<N<<endl;
 for(i=1;i<=N;i++){
    scanf("%d %d ",&V[i],&m);if(!m) V[i]=-V[i];}
    for(i=N+1;i<=2*N;i++)
    V[i]=V[i-N];
  //for(i=1;i<=2*N;i++)  printf("%d %d \n",V[i],m);
}

void proceseaza()
{ 
  int i,j,s1,s2;
  for(s1=1,s2=1,i=1;i<=2*N;i++)
    { j=i;
      X[j]=X[j-1]+V[j];;
     while (s1<=s2 && deque[s2]>X[j]) s2--;
     s2++;
     deque[s2]=X[j];
     poz[s2]=j;
     while (s1<=s2 && poz[s1]+U-L<j) s1++;
     query[j]=poz[s1];
    }

  REZ=-INF; ;
  for(i=L;i<=2*N;i++)
     {
       j=query[i-L];
       if (X[i]-X[j]>REZ)
     {REZ=X[i]-X[j];pA=j+1;pB=i;}
     }

     cout<<REZ<< ' '<<pA<<pB-pA+1<<endl;
}


void afiseazaRez()
{
 freopen("buline.out","w",stdout);
 //if (pB>N)pB-=N;
 printf("%ld\n%d %d\n",REZ,pA,pB-pA+1);
}

int main()
{
 citesteDate();
 proceseaza();
 afiseazaRez();
 return 0;
}