Cod sursa(job #342405)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 21 august 2009 16:29:21
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<cstdio>
#define N 200001
int n,s,maxim=-N,lung,p,poz;
struct {short int val;int s;}v[N];
void circ()
{
	int cn=2*n;
	int max1=-N,pozm,sum;
	for (int i=n+2; i<cn;++i)
	{
		if (max1<v[i-n-1].s)
		{
			max1=v[i-n-1].s;
			pozm=i-n-1;
		}
		sum=v[n].s-v[i-n-1].s+max1;
		if (maxim<sum)
		{
			maxim=sum;
			poz=i-n;
			lung=n-i+n+1+pozm;
			continue;
		}
		if (sum==maxim)
		{
			if (pozm==poz)
				if (lung>n-i+n+1+pozm)
					lung=n-i+n+1+pozm;
				else
					if (poz>pozm)
					{
						poz=i-n;
						lung=n-i+n+1+pozm;
					}
		}
	}
}
void citire()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	scanf("%d",&n);
	int x;
	short int y;
	for (int i=1; i<=n; ++i)
	{
		scanf("%d%hd",&x,&y);
		if (y)
			v[i].val=x;
		else
			v[i].val=x*(-1);
		v[i].s=v[i-1].s+v[i].val;
		s+=v[i].val;
		if (s>maxim)
		{
			maxim=s;
			poz=p+1;
			lung=i-p;
		}
		if (s<0)
		{
			s=0;
			p=i;
		}
	}
	circ();
	printf("%d %d %d",maxim,poz,lung);
}
int main()
{
	citire();
	return 0;
}