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

using namespace std;

struct nd {
	int p, s, c, f;
};

int n, c, id, smallm, m;

nd calcNode (nd a, nd b) {
	nd res;
	res.p = max(a.p, a.f + b.p);
	res.s = max(b.s, b.f + a.s);
	res.c = max(max(a.c, b.c), a.s + b.p);
	res.f = a.f + b.f;
	return res;
}

nd calcSubtree(int x) {
	nd res;
	if (x >= m) {
		if (x - m >= n) {
			res.p = res.s = res.c = res.f = 0;
		} else {
			int cv = ElementAt(x - m + 1);
			if (cv >= 0) {
				res.p = res.s = res.c = cv;
			} else {
				res.p = res.s = res.c = 0;
			}
			res.f = cv;
		}
	} else {
		res = calcNode(calcSubtree(2*x), calcSubtree(2*x+1));
	}

	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	n = Size();
	c = NumberOfNodes();
	id = MyNodeId();

	m = 1;
	while (m < c) {
		m = (m << 1);
	}

	smallm = m;
	m = 1;
	while (m < n) {
		m = (m << 1);
	}

	if (n <= c) {
		if (id == 0) {
			nd result = calcSubtree(1);
			cout << result.c << endl;
		}
	} else {
		vector<int> subtrees;
		int st = 0, i = 0;
		while (i < 2) {
			st = smallm + id + i * c;
			if (st < smallm * 2) {
				subtrees.push_back(st);
				i++;
			} else {
				break;
			}
		}

		int central = c - 1;
		for (int i = 0; i < subtrees.size(); i++) {
			nd pres = calcSubtree(subtrees[i]);
			PutInt(central, subtrees[i]);
			PutInt(central, pres.p);
			PutInt(central, pres.s);
			PutInt(central, pres.c);
			PutInt(central, pres.f);
			Send(central);
		}

		if (id == central) {
			nd t[2*smallm];
			int counter = 0;
			for (int i = 0; i < smallm; i++) {
				int sender = Receive(-1);
				int stix = GetInt(sender);
				t[stix].p = GetInt(sender);
				t[stix].s = GetInt(sender);
				t[stix].c = GetInt(sender);
				t[stix].f = GetInt(sender);
			}

			for (int i = smallm - 1; i > 0; i--) {
				t[i] = calcNode(t[i*2], t[i*2+1]);
			}

			cout << t[1].c << endl;
		}
	}

	return 0;
}