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
#include "maklib.h"

#include <algorithm>
#include <iostream>
#include <cstdio>
#include "message.h"
using namespace std;

int main() {
	long long int n = Size();
	long long int nodes = NumberOfNodes();
	long long int work = max(n / nodes + 1, (long long int)10e7);
	long long int MyNodeIdx = MyNodeId();
	long long int result = 0;
	long long int maxi = 0;
	long long int begining = 0;
	long long int beginingMax = 0;
	long long int end = 0;
	long long int endMax = 0;
	long long int overall = 0;
	for(long long int i = 1 + MyNodeIdx * work; i < 1 + (MyNodeIdx + 1) * work && i <= n; i++){
			int tmp = ElementAt(i);
			overall += tmp;
			if(result > 0){
				result += tmp;
			}else{
				result = tmp;
			}
			begining += tmp;
			if(begining > beginingMax){
				beginingMax = begining;
			}
			if(result > maxi){
				maxi = result;
			}
	}
	if(1 + MyNodeIdx * work <= min(n,(MyNodeIdx + 1) * work)){
		for(long long int i = min(n,(MyNodeIdx + 1) * work); i >= 1 + MyNodeIdx * work; i--){
				end += ElementAt(i);
				if(end > endMax){
					endMax = end;
				}
		}
	}
	if(nodes == 1){
		printf("%lld\n", maxi);
	}else{
		if(MyNodeIdx == 0){
			PutLL(1, maxi);
			Send(1);
			PutLL(1, endMax);
			Send(1);
		}
		for(long long int i = 1; i < nodes - 1; i++){
			if(MyNodeIdx == i){
				Receive(i - 1);
				long long int maxi_new = GetLL(i - 1);
				Receive(i - 1);
				long long int best_new = GetLL(i - 1);
				if(maxi_new > maxi){
					maxi = maxi_new;
				}
				if(beginingMax + best_new > maxi){
					maxi = beginingMax + best_new;
				}
				PutLL(i + 1, maxi);
				Send(i + 1);
				PutLL(i + 1, max(endMax, overall + best_new));
				Send(i + 1);
			}
		}
		if(MyNodeIdx == nodes - 1){
			Receive(nodes - 2);
			long long int maxi_new = GetLL(nodes - 2);
			Receive(nodes - 2);
			long long int best_new = GetLL(nodes - 2);
			if(maxi_new > maxi){
				maxi = maxi_new;
			}
			if(beginingMax + best_new > maxi){
				maxi = beginingMax + best_new;
			}
			printf("%lld\n", maxi);
		}
	}
 	return 0;
}