Cod sursa(job #213515)

Utilizator ilincaSorescu Ilinca ilinca Data 10 octombrie 2008 00:42:01
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <stdio.h>

#define MAXN 200001


struct sume
{
	int s;//suma optima pana la pozitia i
	int p;//pozitia la care se afla ultimul element din s
};


int n, p, l, max, v [MAXN], s [MAXN];
sume t [MAXN];


void scan ()
{
	int i, tip;
	scanf ("%d", &n);
	scanf ("%d%d", v+1, &tip);
	if (tip == 0)
		v [1]*=(-1);
	s [1]=v [1];
	t [1].s=v [1];
	t [1].p=1;
	for (i=2; i<=n; ++i)
	{
		scanf ("%d%d", v+i, &tip);
		if (tip == 0)
			v [i]*=(-1);
		s [i]=s [i-1]+v [i];
		if (s [i] > t [i-1].s)
		{
			t [i].s=s [i];
			t [i].p=i;
		}
		else
		{
			t [i].s=t [i-1].s;
			t [i].p=t [i-1].p;
		}
	}
}

void sum1 ()
{
	int sc=0, i, poz=1;
	for (i=1; i<=n; ++i)
	{
		sc+=v [i];
		if (sc > max)
		{
			max=sc;
			p=poz;
			l=i-poz+1;
		}
		if (sc < 0)
		{
			poz=i+1;
			sc=0;
		}
	}
}

void sum2 ()
{
	int i, x;
	for (i=1; i<=n; ++i)
	{
		x=t [i-1].s+s [n]-s [i-1];
		if (max < x)
		{
			max=x;
			p=i;
			l=n-i+1+t [i-1].p;
		}
	}
}

int main ()
{
	freopen ("buline.in", "r", stdin);
	freopen ("buline.out", "w", stdout);
	scan ();
	sum1 ();//sumele posibile daca nu sunt sub forma de cerc
	sum2 ();
	printf ("%d %d %d\n", max, p, l);
	return 0;
}