Cod sursa(job #29760)

Utilizator vrajalaMihai Viteazu, razboinicu luminii vrajala Data 9 martie 2007 21:54:25
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#include <stdlib.h>
#define nmax 200000

int b[nmax],k,lmax,pmax,p;
long n,i,s,sum[nmax],best[nmax],max;

int main()
{
 freopen("buline.in","r",stdin);
 scanf("%ld\n",&n);
 for (i=0;i<n;++i)
     {
      scanf("%d %d\n",&b[i],&k);
      if (k==0) b[i]*=-1;
     }
 fclose(stdin);
 p=0;
 s=b[0];
 max=s;
 pmax=1;
 lmax=1;
 sum[0]=b[0];
 best[0]=0;
 for (i=1;i<n;++i)
     {
     sum[i]=sum[i-1]+b[i];
     if (sum[i]>sum[best[i-1]]) best[i]=i;
        else best[i]=best[i-1];
     if (s+b[i]>b[i]) s+=b[i];
        else {
             s=b[i];
             p=i;
             }
     if (s>max)
        {
        max=s;
        pmax=p;
        lmax=i-p+1;
        }
     }
     --n;
     for (i=0;i<n;++i)
         {
         if ((sum[best[i]]+sum[n]-sum[i]>max)||((sum[best[i]]+sum[n]-sum[i]==max)&&(i<pmax))||((sum[best[i]]+sum[n]-sum[i]==max)&&(i==pmax)&&(n-i+best[i]<lmax)))
            {
            max=sum[best[i]]+sum[n]-sum[i];
	    pmax=i+1;
	    lmax=n-i+best[i]+1;
	    }
	 }
      freopen("buline.out","w",stdout);
      printf("%ld %d %d",max,pmax+1,lmax);
      return 0;
}