Cod sursa(job #741853)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 27 aprilie 2012 10:49:14
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>

#define MAXN 400001

int A[MAXN], Deque[MAXN];
long long S[MAXN], Maxim;
int N, st, dr;
int i, front, back, 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) x = -x;
		A[i] = x;
		A[i+N] = x;
	}
	
	for (i=1; i<=2*N; ++i)
		S[i] = S[i-1] + A[i];
	
	front = 1; back = 0; Maxim = S[N]; st = 1; dr = N;
	for (i=1; i <= 2*N; ++i){
		while (front <= back && Deque[front] < i - N)
			++front;
		if (Maxim < S[i] - S[Deque[front]]){
			Maxim = S[i] - S[Deque[front]];
			st = Deque[front] + 1;
			dr = i;
		}
		while (front <= back && S[Deque[back]] > S[i])
			--back;
		Deque[++back] = i;
	}
	
	printf("%lld %d %d\n", Maxim, st, dr-st+1);
	
	return 0;
}