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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
//wersja rozproszona
#include "maklib.h"

#include <iostream>
#include <cstdint>
#include <cmath>

#include "message.h"

using namespace std;


#ifdef _MSC_VER
inline double round(double n){
	return n>=0 ? floor(n+0.5) : ceil(n-0.5);
}
#endif

struct Sums{
	int64_t leftSum;
	int64_t middleSum;
	int64_t rightSum;
};

struct Range{
	int32_t iBegin;
	int32_t iEnd;
};

int64_t computeSum(Range range);

Sums computeSums(Range range);

int64_t computeMaxSum(Range range, Range &maxRange);

Range getRangeOfSubtable();

Sums synchronizeSums(Sums currentSum);

int32_t getNumberOfUsefulNodes();

int main(){
	ios_base::sync_with_stdio(0);
	int k = getNumberOfUsefulNodes();
	if(MyNodeId()<k){
		Range range = getRangeOfSubtable();
		Sums sums = computeSums(range);
		sums = synchronizeSums(sums);
		if(MyNodeId()==(k-1)){
			cout<<sums.middleSum<<endl;
		}
	}
}


/*
	range - range to compute
	returns sum of subtable elements specified by range
*/
int64_t computeSum(Range range){
	int64_t sum=0;
	for(int32_t i=range.iBegin;i<range.iEnd;++i){
		sum+=ElementAt(i);
	}
	return sum;
}


/*
	range - range to compute
	returns Sums: sum of subtable left to the max, sum of max subtable, sum of subtable right to the max
*/
Sums computeSums(Range range){
	Sums sums;
	Range maxRange;

	sums.middleSum=computeMaxSum(range,maxRange);

	Range leftRange;
	leftRange.iBegin=range.iBegin;
	leftRange.iEnd=maxRange.iBegin;

	Range rightRange;
	rightRange.iBegin=maxRange.iEnd;
	rightRange.iEnd=range.iEnd;

	sums.leftSum = computeSum(leftRange);
	sums.rightSum = computeSum(rightRange);

	return sums;
}


/*
	range - range to compute
	maxRange - range of computed max subtable will be saved here
	returns - sum of max subtable
*/
int64_t computeMaxSum(Range range, Range &maxRange){
	Range currentRange; //range to represent current subtable
	currentRange.iBegin=range.iBegin;
	currentRange.iEnd=range.iBegin+1;
	int64_t currentSum=0; //sum of current subtable
	int64_t maxSum=0; //sum of computed max subtable
	maxRange.iBegin=range.iEnd;
	maxRange.iEnd=range.iEnd;

	for(int i=range.iBegin;i<range.iEnd;++i){
		if(currentSum>0){
			currentSum+=ElementAt(i);
			++currentRange.iEnd;
		}
		else{
			currentSum=ElementAt(i);
			currentRange.iBegin=i;
			currentRange.iEnd=i+1;
		}
		if(currentSum>maxSum){
			maxSum=currentSum;
			maxRange.iBegin=currentRange.iBegin;
			maxRange.iEnd=currentRange.iEnd;
		}
	}

	return maxSum;
}

/*
	Returns range of subtable that this machine should compute
*/
Range getRangeOfSubtable(){
	int32_t n; //number of numbers in table
	int32_t k=getNumberOfUsefulNodes();
	n = Size();
	double perMachine = static_cast<double>(n)/k;
	Range range;
	range.iBegin=static_cast<int32_t>(round(MyNodeId()*perMachine))+1; //first element index
	range.iEnd=static_cast<int32_t>(round((MyNodeId()+1)*perMachine))+1; //last element index  // <iBegin,iEnd)
	return range;
}

/*
	Compute max of current subtable and subtable computed with machine id less than current
	After that sends computed max to the next machine (if there is any)
	Returns computed max
*/
Sums synchronizeSums(Sums currentSum){
	Sums globalBest=currentSum;
	Sums currentBest=currentSum;
	if(MyNodeId()>0){
		int32_t previous = MyNodeId()-1;
		Receive(previous);
		Sums previousSum;
		
		globalBest.leftSum=GetLL(previous);
		globalBest.middleSum=GetLL(previous);
		globalBest.rightSum=GetLL(previous);
		previousSum.leftSum=GetLL(previous);
		previousSum.middleSum=GetLL(previous);
		previousSum.rightSum=GetLL(previous);

		if(previousSum.middleSum+previousSum.rightSum+currentSum.leftSum > 0){
			currentBest.leftSum=previousSum.leftSum;
			currentBest.middleSum=previousSum.middleSum+previousSum.rightSum+currentSum.leftSum+currentSum.middleSum;
			currentBest.rightSum=currentSum.rightSum;
		}
		else{
			currentBest=currentSum;
		}

		if(currentBest.middleSum>globalBest.middleSum){
			globalBest=currentBest;
		}
	}
	if(MyNodeId()<(getNumberOfUsefulNodes()-1)){
		int32_t next = MyNodeId()+1;
		PutLL(next,globalBest.leftSum);
		PutLL(next,globalBest.middleSum);
		PutLL(next,globalBest.rightSum);
		PutLL(next,currentBest.leftSum);
		PutLL(next,currentBest.middleSum);
		PutLL(next,currentBest.rightSum);
		Send(next);
	}
	return globalBest;
}


int32_t getNumberOfUsefulNodes(){
	return min(Size(),NumberOfNodes());
}