Cod sursa(job #26766)

Utilizator pocaituDavid si Goliat pocaitu Data 5 martie 2007 21:05:40
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<stdio.h>
#define infi 10005
#define nmax 200000
int long max=-infi,s[nmax],n,inc,sf,lung;
void afiseaza();
void citeste()
{int long i,a,b;
 freopen("buline.in","r",stdin);
 scanf("%ld",&n);
 for(i=1;i<=n;i++)
  {scanf("%ld%ld",&a,&b);
   if(!b)
	 s[i]=-a;
   else
	 s[i]=a;
   }
 }

int long caz_1()
{int long i,j,in,coada=0;
 for(i=1;i<=n;i++)
   {coada+=s[i-1];
	if(coada<=0)
	  {coada=0;in=i;}
	if(coada+s[i]>max)
	  {max=coada+s[i];
	   inc=in;
	   sf=i;
	   lung=sf-inc+1;
	   }
	}
 }
void caz_2()
{int long i,sff[nmax],incc[nmax],s1[nmax],s2[nmax],ma1[nmax],ma2[nmax];
 for(i=0;i<=n+1;i++)
	 ma1[i]=ma2[i]=-infi;
 s2[n+1]=s1[0]=0;
 for(i=1;i<=n;i++)
   {s1[i]=s1[i-1]+s[i];
	if(s1[i]>ma1[i-1])
	 {ma1[i]=s1[i];
	  sff[i]=i;
	  }
	else
	  {ma1[i]=ma1[i-1];
	  sff[i]=sff[i-1];
	  }
	}

 for(i=n;i>=1;i--)
   {s2[i]=s2[i+1]+s[i];
	if(s2[i]>ma2[i+1])
	  {ma2[i]=s2[i];
	   incc[i]=i;
	   }
	else
	  {ma2[i]=ma2[i+1];
	   incc[i]=incc[i+1];
	   }
	}
 for(i=1;i<n-1;i++)
  if(ma1[i]+ma2[i+2]>max)

	 {max=ma1[i]+ma2[n-i-1];
	  inc=incc[n-i-1];
	  sf=sff[i];
	  lung=sf+n-inc+1;
	  }

 }


int main()
{citeste();
 //caz_1();
 caz_2();
 afiseaza();
 return 0;
 }
void afiseaza()
{freopen("buline.out","w",stdout);
 printf("%ld %ld %ld",max,inc,lung);
 fclose(stdout);


 }