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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include "message.h"
#include "maklib.h"
#include <math.h>

#include <iostream>
using namespace std;

struct El {  
	long long int Max;
	long long int Beg;
	long long int Sum;
	long long int End;
	
	El() {
		Max = Beg = Sum = End = 0;
	}
};

int main() {

	long long int s = 1 + round((double)Size() / (double)NumberOfNodes()) * MyNodeId();
	long long int e = round((double)Size() / (double)NumberOfNodes()) * (MyNodeId() + 1);
	
	if (MyNodeId() == NumberOfNodes() - 1) {
		e = Size();
	}
	
	if (Size() < NumberOfNodes() && MyNodeId() != 0) {
		return 0;
	}
	
	if (Size() < NumberOfNodes()) {
		s = 1;
		e = Size();
	}
		
	long long int End, Beg, Max, Sub, Sum, Cur;

	End = Beg = Max = Sub = Sum = 0;

	for (int i = s; i <= e; i++) {
		Cur = ElementAt(i);
		Sub += Cur;
		End = Sub;
		Sum += Cur;

		if (Sum > Beg)
			Beg = Sum;
		if (Sub > Max)
			Max = Sub;
		else if (Sub <= 0)
			Sub = 0;
	}
	
	if (Size() < NumberOfNodes()) {
		cout << Max;
		return 0;
	}
	
	/*
	if (MyNodeId() == 1) {
		cout << "  " << Max << endl;
		cout << Beg << " " << Sum << " " << End << endl;
	}
	*/
	
	// Złączanie
	if (MyNodeId() != 0) {
		PutLL(0, Max);
		PutLL(0, Beg);
		PutLL(0, Sum);
		PutLL(0, End);
		Send(0);
		return 0;
	}

	El *elementy = new El[NumberOfNodes()];
	
	El ele;
	ele.Max = Max;
	ele.Beg = Beg;
	ele.Sum = Sum;
	ele.End = End;
	
	elementy[0] = ele;
	
	for (int instancja = 1; instancja < NumberOfNodes(); ++instancja) {
		El ele;
		Receive(instancja);
		ele.Max = GetLL(instancja);
		if (ele.Max > Max)
			Max = ele.Max;
		ele.Beg = GetLL(instancja);
		ele.Sum = GetLL(instancja);
		ele.End = GetLL(instancja);
		elementy[instancja] = ele;
    }
	
	Sub = 0;
	
	ele = elementy[0];
	
	if (ele.End > 0) Sub = ele.End;
	
	for (int instancja = 1; instancja < NumberOfNodes(); ++instancja) {
		
		ele = elementy[instancja];
		if (Sub + ele.Beg > Max)
			Max = Sub + ele.Beg;
		if (ele.Sum < 0)
			Sub = 0;
		if (ele.Sum >= 0) {
			if (ele.Sum >= ele.End)
				Sub += ele.Sum;
			else
				Sub = ele.End;
		} else {
			if (ele.End > 0)
				Sub = ele.End;
			else
				Sub = 0;
		}
	}
	
	cout << Max;
	
	return 0;
}