Cod sursa(job #503673)

Utilizator thebest001Neagu Rares Florian thebest001 Data 24 noiembrie 2010 12:04:29
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
using namespace std;

int S[400001], St[400001], max;
int Poz[400001];
int i, j, N, NN, nr, cul;
int s1, s2, pmax, lmax;


ifstream in("buline.in");
ofstream out("buline.out");

void add(long long e, int pz)
{
	while (s2 >= s1 && St[s2] > e) s2--;

	s2++;

	St[s2] = e;
	Poz[s2] = pz;

	if (pz - Poz[s1] + 1 > N) s1++;
}

int main()
{
	long long max;
	in>>N;
	for (i = 1; i <= N; i++)
	{
		in>>nr>>cul;
		if (cul == 0) nr =  -nr; 
		
		S[i] = S[i - 1] + nr;
	}		
	
	NN = N;
	
	for (i = 1; i < N; i++)
		S[++NN] = S[i] + S[N];
	
	s1 = s2 = 0;
	
	max = -2000001;
	
	for (i = 1; i < NN; i++)
	{
		if (max < S[i] - St[s1])
		{
			max = S[i] - St[s1];
			pmax = Poz[s1] + 1;
			lmax = i - pmax + 1;
		}
		
		add(S[i], i);
	}
	
	out<<max<<" "<<pmax<<" "<<lmax;
	return 0;
}