Cod sursa(job #1076908)

Utilizator GaborGabrielFMI - GabrielG GaborGabriel Data 10 ianuarie 2014 18:31:47
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <fstream>
using namespace std;

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


#define MAXN 200005
int v[MAXN], modificat[MAXN], culoare[MAXN], N;


int main()
{
	int i, tip, numar, max = 0, max_poz = 0, max_incep, max_lung;

	// Read the input
	f >> N;
	for (i = 1; i <= N; ++i)
	{
		f >> numar >> tip;
		if (tip) v[i] = numar;
		else v[i] = numar * (-1);
	}

	// Skipt the first negative numbers
	i = 1;
	while (v[i] < 0) modificat[i] = v[i], ++i;

	// Find the maximum succession
	while (i<=N)
	{
		modificat[i] = v[i];
		culoare[i] = culoare[i - 1] + 1;
		if (modificat[i - 1] > 0 && modificat[i - 1] + v[i] > 0)
		{
			modificat[i] += modificat[i - 1];
			culoare[i] = culoare[i - 1];
		}

		if (modificat[i] > max)
		{
			if (culoare[max_poz] == culoare[i])
				max_lung += i - max_poz, max_poz = i;
			else
				max_incep = max_poz = i, max_lung = 1;
			max = modificat[i];
		}

		++i;
	}

	if (culoare[max_poz] == culoare[N] && culoare[N] != culoare[1] && modificat[N] + v[1] > 0)
	{
		modificat[1] = modificat[N] + v[1];
		culoare[1] = culoare[N];
		if (modificat[1] > max)
			max_lung++, max_poz = 1, max = modificat[1], culoare[1] = culoare[N];

		i = 1;
		while (++i < max_incep && modificat[i-1] + v[i] > 0 && culoare[i-1] != culoare[i])
		{
			modificat[i] = modificat[i-1] + v[i];
			culoare[i] = culoare[i - 1];
			if (modificat[i] > max)
				max_lung += (max_poz + i) % N, max_poz = i, max = modificat[i];
		}
	}

	g << max << ' ' << max_incep << ' ' << max_lung << '\n';
	return 0;
}