Cod sursa(job #320678)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 5 iunie 2009 14:45:27
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include<stdio.h>
int n,k,i,a[400001],i1,t,ok,max=-10000;
char b[400001]; 

void smax()
{  int s=1,gs=1,gd=1,i,p=0,j=0;
   long long lmax=1,gmax=0;
   
   for(i=2;i<=n+n;i++) { if(lmax>0&&!b[i]) { lmax=lmax+a[i];
                                              b[n+i]=1;
                                              b[n+i-1]=1;
                                              p++;
                                              b[p]=n+i;
                                              b[p-1]=n+i-1;
                                            }    
                      else { lmax=a[i];
                             s=i;
                             for(j=p;j>=0;--j) b[b[j]]=0;
                             p=0;
                           }
                           
                      if(lmax>gmax) { gmax=lmax;
                                      gs=s;
                                      gd=i;
                                    }
                    }                
  printf("%lld ",gmax);
  printf("%d ",gs);
  printf("%d\n",gd-gs+1);
}                                
 
int main()
{  freopen("buline.in","r",stdin);
   freopen("buline.out","w",stdout);
   scanf("%d",&n);
   for(i1=1;i1<=n;i1++) { scanf("%d %d",&t,&k);
                          i++;                    
                          if(!k) a[i]=-t;
                          else  { a[i]=t;
                                  ok=1;
                                }  
                          a[i+n]=a[i];
                     }
   if(ok) smax();
   else{ t=0;
          for(i=1;i<=n;i++) if(a[i]>max) { max=a[i];
                                           t=i;
                                         }   
          printf("%d %d 1\n",max,t);
         }   
   fclose(stdin);
   fclose(stdout);                  
   return 0;
}