Cod sursa(job #29381)

Utilizator judy_kCristina Petrovici judy_k Data 9 martie 2007 10:39:31
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>

int T[400010];
int S_Max,S_C,begin,end,poz_beg,i,n,x,y;

int main()
{
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
    {
    	scanf("%d %d",&x,&y);
        if (y==0) T[i]=-x;
        else T[i]=x;
    }

    for (i=n+1;i<=2*n-1;++i)
    	T[i]=T[i-n];
    n=2*n-1;

	S_Max=T[1];
	S_C=S_Max;
	poz_beg=1;
	begin=1;
	end=1;
	for (i=2;i<=n;++i)
    {
		if (S_C<0)
        {
			S_C=T[i];
			poz_beg=i;
        }
		else
			S_C=S_C+T[i];
		if (S_Max<S_C)
        {
			S_Max=S_C;
			begin=poz_beg;
			end=i;
        }
        if (S_Max==S_C && i-poz_beg<end-begin)
        {
            begin=poz_beg;
            end=i;
        }
    }

	printf("%d %d %d\n",S_Max, begin, end-begin+1);
}