Cod sursa(job #353851)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 6 octombrie 2009 15:33:03
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<iostream>
#include<string>

using namespace std;

#define nm 200005
#define inf 1000000001

int a[nm],sum[nm],best[nm],lb[nm];

inline int rs(int a,int b)
{
       return sum[b]-sum[a-1];
}

int main()
{
    int n,s,i,ans=-inf,anss,ansl;
    
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    
    scanf("%d",&n);
    
    for(i=1;i<=n;++i)
    {
      scanf("%d %d",&a[i],&s);
      if(!s) a[i]*=(-1);
      sum[i]=sum[i-1]+a[i];
    }
        
    for(i=n;i>=1;--i)
      if(best[i+1]>=rs(i,n)) 
      {
        best[i]=best[i+1];
        lb[i]=lb[i+1];
      }
      else 
      {
        best[i]=rs(i,n);
        lb[i]=n-i+1;
      }
      
    int sump=-inf,l=0;
    
    for(i=1;i<=n;++i)
    {
      if(sump+a[i]>a[i])
      {
        sump+=a[i];
        ++l;
      }
      else
      {
        sump=a[i];
        l=1;
      }
      
      if(sump>ans)
      {
        ans=sump;
        anss=i-l+1;
        ansl=l;
      }
      else if(sump==ans) if(i-l+1<anss) 
                         {
                           anss=i-l+1;
                           ansl=l;
                         }
                         else if(i-l+1==anss) if(l<ansl) ansl=l;
      int as=sum[i]+best[i+1],ass=n-lb[i+1]+1,asl=i+lb[i+1];
      
      if(as>ans)
      {
        ans=as;
        anss=ass;
        ansl=asl;
      }          
      else if(as==ans) if(ass<anss)
                       {
                         anss=ass;
                         ansl=asl;
                       }          
                       else if(ass==anss) if(asl<ansl) ansl=asl;  
    }
    
    
    printf("%d %d %d",ans,anss,ansl);
    
    return 0;
}