1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
//Potyczki 2014 MAK runda rozproszona probna
#include <algorithm>
#include <iostream>
#include <cmath>

#include "maklib.h"
#include "message.h"

using namespace std;

typedef long long ll;

struct Wynik
{
	ll suma;
	int s, k; //znacznik start i koniec max podsumy
};

Wynik MaxSum(int b, int e)
{
	Wynik w = { 0, 0,0 };

	ll m = 0, s = 0;
	int si = 0, ki = 0;
	for (int a = b; b < e; a++)
	{
		s = max(ll(0), s + ElementAt(a));
		if (s == 0) //gdy suma sie nie zwieksza 
			si = a + 1; //zaczynamy podciag od nastepnego elementu
		if (m < s) //nowa suma nowy koniec podciagu
			ki = a;
		m = max(m, s);
	}
	w.suma = m;

	if (si <= ki) //suma != 0
	{
		if (si == 0) //poczatek
			w.s = 1;
		if (ki == e-1) //koniec
			w.k = 1;
	}
	return w;
}

int main(int, char**)
{
	ios_base::sync_with_stdio(0);

	int s = Size(),
		id = MyNodeId(),
		idnum = NumberOfNodes(),
		part = int(ceil(s / idnum));

	int start = id*part,
		end = min(start + part, s);

	Wynik w = {};
	if (start < s)
		w = MaxSum(start, end);
	else
		w = { -1, 0, 0 };

	if (id != 0)
	{
		PutInt(0, w.s);
		PutLL(0, w.suma);
		PutInt(0, w.k);
		Send(0);
	}
	else
	{
		//a == 0
		Wynik prev = w;
		ll maxel = w.suma, //najwiekszy pojedynczy element
			maxs = w.suma, //obecnie najwieksza suma
			pmaxs = w.suma; //poprzednia najwiesza suma

		for (int a = 1; a < idnum; a++)
		{
			int n = Receive(a);
			Wynik tmp;
			tmp.s = GetInt(a);
			tmp.suma = GetLL(a);
			tmp.k = GetInt(a);

			if (tmp.suma < 0)
				break;

			//najwiekszy z pojedynczych
			maxel = (tmp.suma > maxel) ? tmp.suma : maxel;

			//koniec poprzedniego i poczatego obecnego
			if (prev.k == 1 && tmp.s == 1) //mozemy laczyc
				maxs += tmp.suma;
			else //nie mozna laczyc
			{
				pmaxs = maxs;
				maxs = tmp.suma;
			}
			prev = tmp;
		}
		ll m = max(max(maxs, pmaxs), maxel);
		cout << m << endl;
	}
	return 0;
}