Cod sursa(job #470219)

Utilizator darrenRares Buhai darren Data 12 iulie 2010 13:17:06
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<fstream>
using namespace std;

const int INF = ~(1LL << 60);

int n, a[200001], p1, p2;
long long sum = INF;

int main()
{
	ifstream fin("buline.in");
	ofstream fout("buline.out");
	fin >> n;
	for (int i = 1, x1, x2; i <= n; ++i)
	{
		fin >> x1 >> x2;
		a[i] = x1 * (x2 == 0 ? -1 : 1);
	}
	
	int sact = a[1], pa1 = 1;
	for (int i = 2; i <= n; ++i)
	{
		if (sact < 0) sact = a[i], pa1 = i;
		else          sact += a[i];
		
		if (sact > sum)
			sum = sact, p1 = pa1, p2 = i;
		
		if (i == n && sact > 0)
			for (int j = 1; j < pa1 && sact > 0; ++j)
			{
				sact += a[j];
				if (sact > sum)
					sum = sact, p2 = j;
			}
	}
	
	int lung;
	if (p2 > p1) lung = p2 - p1 + 1;
	else         lung = p2 + n - p1 + 1;
	
	fout << sum << ' ' << p1 << ' ' << lung;
}