#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; } }
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; } } |