Cod sursa(job #26195)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 5 martie 2007 12:37:30
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <stdio.h>

#define maxn 400010
#define maxv -10000

int n,s,p;
short a[maxn];
int sum[maxn],smax[maxn],ind[maxn];
int sol,pos,l;

int main()
{
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    
    scanf("%d ",&n);
    int i,semn;
    
    for (i=1;i<=n;i++)
    {
        scanf("%d %d ",&a[i],&semn);
        if (!semn) a[i]=-a[i];
    }
    
    for (i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
    
    for (i=1;i<=n;i++) 
      if (smax[i-1]>sum[i]) 
      {
          smax[i]=smax[i-1];
          ind[i]=ind[i-1];
      }
      else {
               smax[i]=sum[i];
               ind[i]=i;
           }
    
    for (i=1;i<=n;i++)
    {
        if (s<=0) 
        {
            s=0;
            p=i;
        }
        
        s+=a[i];
        if (s>sol) 
        {
           sol=s;
           pos=p;
           l=i-p+1;
        } 
    }
    
    for (i=1;i<=n;i++)
      if (sum[n]-sum[i-1]+smax[i-1]>sol)
      {
           sol=sum[n]-sum[i-1]+smax[i-1];
           pos=i;
           l=n+ind[i-1]-i+1;
      }
    
    printf("%d %d %d\n",sol,pos,l);
    
    return 0;
}