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
#include <iostream>
#include <algorithm>
#include "kanapka.h"
#include "message.h"
#define LL long long

using namespace std;

LL N, from, to;
int id, K;

void load () {
    N = GetN ();
    id = MyNodeId ();
    K = NumberOfNodes ();
    
    LL base_len = N / K;
    LL longer = N % K;
    from = base_len * id + min ((LL) id, longer);
    to = from + base_len - 1 + (longer > (LL) id ? 1 : 0); 
}

struct dp {
    LL answer, sum, max_pref, max_suf;
};

dp simple (LL a) {
    dp b;
    b.sum = a;
    b.max_pref = b.max_suf = b.answer = max (a, 0ll);
    return b;
}

dp merge (dp a, dp b) {
    dp c;
    c.answer = max (a.max_pref + b.max_suf, max (a.sum + b.answer, b.sum + a.answer));
    c.sum = a.sum + b.sum;
    c.max_pref = max (a.max_pref, a.sum + b.max_pref);
    c.max_suf = max (b.max_suf, b.sum + a.max_suf);
    return c;
}

dp solve (LL from, LL to) {
    dp ans = simple (0);
    for (LL i = from; i <= to; ++i) {
	dp cur = simple (GetTaste (i));
	ans = merge (ans, cur);
    }
    return ans;
}

void SendDP (int target, dp val) {
    PutLL (target, val.answer);
    PutLL (target, val.sum);
    PutLL (target, val.max_pref);
    PutLL (target, val.max_suf);
    Send (target);
}

dp GetDP (int target) {
    dp a;
    Receive (target);
    a.answer = GetLL (target);
    a.sum = GetLL (target);
    a.max_pref = GetLL (target);
    a.max_suf = GetLL (target);
    return a;
}

int main () {
    load ();
    dp part = solve (from, to);
    if (id) {
	SendDP(0, part);
    }
    else {
	for (int i = 1; i < K; ++i) {
	    dp cur = GetDP (i);
	    part = merge (part, cur);
	}
	cout << part.answer << endl;
    }
}