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
#include <cstdio>
#include <queue>
#include "dzialka.h"
#include "message.h"
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define SIZE(c) ((int)(c).size())

typedef long long LL;

LL res[2][75001];
queue<LL> in, out;

int main() {
	int n = GetFieldHeight(), m = GetFieldWidth();
	int nodes = NumberOfNodes(), node = MyNodeId();
	int a = m * node / nodes, b = m * (node + 1) / nodes;
	LL r = 0;
	REP(i,n) {
		int ii = i & 1;
		if (node) {
			if (in.empty()) {
				Receive(node - 1);
				int size = GetInt(node - 1);
				REP(s,size) in.push(GetLL(node - 1));
			}
			res[ii ^ 1][0] = in.front();
			in.pop();
		}
		FOR(j,a,b) {
			int jj = j - a;
			if (IsUsableCell(i, j)) {
				LL x = res[ii][jj + 1] + res[ii ^ 1][jj];
				if (x) x -= res[ii][jj];
				++x;
				res[ii ^ 1][jj + 1] = x;
				r += x;
			} else
				res[ii ^ 1][jj + 1] = 0;
		}
		if (node < nodes - 1) {
			out.push(res[ii ^ 1][b - a]);
			if (SIZE(out) == 76) {
				PutInt(node + 1, SIZE(out));
				while (!out.empty()) {
					PutLL(node + 1, out.front());
					out.pop();
				}
				Send(node + 1);
			}
		}
	}
	if (!out.empty()) {
		PutInt(node + 1, SIZE(out));
		while (!out.empty()) {
			PutLL(node + 1, out.front());
			out.pop();
		}
		Send(node + 1);
	}
	if (node) {
		Receive(node - 1);
		r += GetLL(node - 1);
	}
	if (node < nodes - 1) {
		PutLL(node + 1, r);
		Send(node + 1);
	} else printf("%lld\n", r);
}