Cod sursa(job #754865)

Utilizator elfusFlorin Chirica elfus Data 3 iunie 2012 21:12:09
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <stdio.h>
#define NMAX 400400

int x[NMAX], S[NMAX], Q[NMAX];

int main()
{
	int i, N, cant, cul, p, u, now, best = (1 << 30) * (-1), X1, X2, bestX1 = 1 << 30, bestX2 = 1 << 30;
	
	freopen("buline.in", "r", stdin);
	freopen("buline.out", "w", stdout);
	
	scanf("%d", &N);
	for (i = 1; i <= N; i++)
	{
		scanf("%d%d", &cant, &cul);
		if (cul)
			x[i] = cant;
		else
			x[i] = cant * (-1);
	}
	
	for (i = N + 1; i <= N + N; i++)
		x[i] = x[i - N];
	for (i = 1; i <= N + N; i++)
		S[i] = S[i - 1] + x[i];
	
	p = 1; u = 0;
	Q[++ u] = 0;
	
	for (i = 1; i <= N + N; i++)
	{
		now = S[i] - S[Q[p]];
		X1 = Q[p] + 1;
		X2 = i - Q[p];
		if ((now > best) || (best == now && X1 < bestX1) || (best == now && X1 == bestX1 && X2 < bestX2))
			best = now, bestX1 = X1, bestX2 = X2;
		while (p <= u && S[i] <= S[Q[u]])
			u --;
		Q[++ u] = i;
		
		if (Q[p] + N == i)
			p ++;
	}
	
	printf("%d %d %d", best, bestX1, bestX2);
	return 0;
}