Cod sursa(job #64890)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 6 iunie 2007 00:47:27
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include<stdio.h>
long long 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("%lld",&n);
 for(i=1;i<=n;i++)
  {
  scanf("%lld %lld",&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]=-2000000001;
 que[1]=b[2];
 frcv[1]=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;
  poz=1;
  lung=n;
 if (max<s-que[1])
   {
   max=s-que[1];
   poz=frcv[1]+1;
   lung=n-poz+2;
   }
 i=2;
 b[1]=s;
 while (i<=n)
   {
   if (que[start]==b[i])
           {
           que[start]=-2000000001;
           start++;
           }
   ss+=a[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;
     }
    if (s-que[start]+ss==max)
     {
     if (poz>frcv[start]+1)
      {
      poz=frcv[start]+1;
     if (i-poz<0)
      lung=i+n-poz+1;
     else
       lung=i-poz+1;
       }
     }
   i++;
   }
 printf("%lld %lld %lld",max,poz,lung);
 return 0;
}