Cod sursa(job #322716)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 9 iunie 2009 17:48:08
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<stdio.h>
int a[400001],b[400001],i,j,st,d,n,x,y,l,mini;
long long s=-2000000000;
int main()
{ freopen("buline.in","r",stdin);
  freopen("buline.out","w",stdout);
  scanf("%d",&n);
  for(i=1;i<=n;i++) { scanf("%d %d",&x,&y);
                      if(!y) a[i]=-x;
                      else a[i]=+x;
                      a[i+n]=a[i];
                    }
  d=0;
  st=1;
  y=2*n-1;
  for(i=1;i<=y;i++) {  a[i]=a[i]+a[i-1];
                      if((a[i]-a[b[st]])>s){ s=(long long)a[i]-(long long)a[b[st]];
                                             mini=b[st]+1;
                                             l=i-b[st];
                                           }
                      while(d>=s&&a[i]<a[b[d]]) d--;
                      d++;
                      b[d]=i;
                      if(a[i-n]==a[b[st]]) st++;
                     } 
 printf("%lld ",s);
 printf("%d ",mini);
 printf("%d\n",l);
 fclose(stdin);
 fclose(stdout);
 return 0;
}