Cod sursa(job #25811)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 4 martie 2007 14:50:09
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>

#define MAXN 400005

int N, x[MAXN], s[MAXN], bst[MAXN], bstp[MAXN];
int d[MAXN], p[MAXN], dl, dr;

void initdeque()
{
	dl = 0; dr = -1;
}

void adddeque( int val, int poz, int L )
{
	for (; dr >= dl && d[dr] >= val; dr--);
	d[ ++dr ] = val;
	p[ dr ] = poz;
	if (poz - p[dl] >= L)
		dl++;
}

int main()
{
	freopen("buline.in", "rt", stdin);
	freopen("buline.out", "wt", stdout);
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
	{
		int val, t;
		scanf("%d %d", &val, &t);
		if (t == 0)
			x[i] = -val;
		else
			x[i] = val;
		s[i] = s[i - 1] + x[i];
	}

	for (int i = N + 1; i < N + N; i++)
		x[i] = x[i - N],
		s[i] = s[i - 1] + x[i];

	initdeque();
	adddeque( s[0], 0, N );
	int MAX = -0x3f3f3f3f, MAXi = -1;
	for (int i = 1; i < N + N; i++)
	{
		bst[i] = s[i] - d[dl];
		bstp[i] = p[dl];

		adddeque( s[i], i, N );
		if (bst[i] > MAX)
		{
			MAX = bst[i];
			MAXi = i;
		}
	}

	printf("%d %d %d\n", MAX, bstp[MAXi] + 1, MAXi - bstp[MAXi]);

	return 0;
}