Cod sursa(job #361248)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 4 noiembrie 2009 12:07:02
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <stdio.h>
#define Nmax 200002

int a[Nmax],s[Nmax],t[Nmax],fin[Nmax];
int n,i,smax,st,lg,semn,sum=-Nmax,stmax,lgmax;

int main(){
	freopen("buline.in","r",stdin);
   freopen("buline.out","w",stdout);
   scanf("%d",&n);
   for(i=1;i<=n;++i){
   	 scanf("%d%d",&a[i],&semn);
       if(semn == 0) a[i] *= -1;
       s[i]=s[i-1]+a[i];
       if(t[i-1] >= s[i] ) t[i]=t[i-1], fin[i]=fin[i-1];
       else t[i]=s[i],fin[i]=i;
   }

   for(i=1;i<=n;++i){
   	if(a[i] > sum+a[i] ) sum=a[i], lg=1, st=i;
      else sum += a[i], lg++;
      if( sum > smax ) smax=sum, stmax=st, lgmax=lg;
   }

   for(i=1;i<=n;++i)
   	if( s[n] - s[i-1] + t[i-1] > smax ){
      	smax = s[n]-s[i-1] + t[i-1];
         stmax = i;
         lgmax = n-i+1 + fin[i-1];
      }

   printf("%d %d %d\n",smax,stmax,lgmax);
   fclose(stdin); fclose(stdout);
   return 0;
}