Cod sursa(job #64814)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 5 iunie 2007 19:30:57
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<stdio.h>
int a[200001],b[200001],n,x,y,j,i,que[200001],s,start,end,max,ss,frcv[200001],poz,lung;
int main()
{
 freopen("buline.in","r",stdin);
 freopen("buline.out","w",stdout);
 scanf("%ld",&n);
 for(i=1;i<=n;i++)
  {
  scanf("%ld %ld",&x,&y);
  if (y==0) a[i]=-x;
      else  a[i]=x;
  }
  for(i=2;i<=n;i++)
   b[i]=b[i-1]+a[i];
  s=b[n]+a[1];
 que[0]=-200001;
 que[1]=b[2];
 start=1;
 end=1;
 for(i=3;i<=n;i++)
 {
   while(b[i]<que[end]) end--;
   end++;
   que[end]=b[i];
   frcv[end]=i;
 }
  max=s;
 if (max<s-que[1]) max=s-que[1];
 i=2;
 b[1]=s;
 while (i<=n)
   {
   if (que[start]==b[i]) start++;
   ss+=b[i];
   if (i>2)
   b[i-1]=b[i-2]+a[i-1];
    while(b[i-1]<que[end]) end--;
    end++;
    que[end]=b[i-1];
    frcv[end]=i-1;
    if (s-que[start]+ss>max)
     {
     max=s-que[start]+ss;
     poz=frcv[start]+1;
     if (i-poz<0)
      lung=i+n-poz+1;
     else
       lung=i-poz+1;
     }
   i++;
   }
 printf("%ld %ld %ld",max,poz,lung);
 return 0;
}