Cod sursa(job #714119)

Utilizator Catah15Catalin Haidau Catah15 Data 15 martie 2012 13:49:44
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;

#define maxN 400010
#define inf (1 << 30)

int A[maxN], sum[maxN];
int D[maxN];


int main()
{
	freopen ("buline.in", "r", stdin);
	freopen ("buline.out", "w", stdout);
	
	int N;
	
	scanf ("%d", &N);
	
	int st = 1, dr = 0;
	
	for (int i = 1; i <= N; ++ i)
	{
		int code;
		
		scanf ("%d %d", &A[i], &code);
		
		if (! code) A[i] = - A[i];
		
		sum[i] = sum[i - 1] + A[i];
		
		while (st <= dr && sum[D[dr]] >= sum[i]) -- dr;
		D[++ dr] = i;
	}
	
	int ans = - inf, start = 0, leng = 0;
	
	for (int i = N + 1; i <= 2 * N; ++ i)
	{
		A[i] = A[i - N];
		sum[i] = sum[i - 1] + A[i];
		
		if (st <= dr && i - D[st] >= N) ++ st;
		
		while (st <= dr && sum[D[dr]] >= sum[i]) -- dr;
		D[++ dr] = i;
		
		if (ans < sum[i] - sum[D[st]])
		{
			ans = sum[i] - sum[D[st]];
			start = D[st] + 1;
			leng = i - start + 1;
		}
		else if (ans == sum[i] - sum[D[st]] && leng > i - (D[st] + 1) + 1)
		{
			start = D[st] + 1;
			leng = i - start + 1;
		}
	}
	
	printf ("%d %d %d", ans, start, leng);
	
	return 0;
}