#include <cstdio> #include <algorithm> #include "message.h" #include "kanapka.h" using namespace std; typedef long long i64; struct monoid_t { i64 total; i64 max_prefix; i64 max_suffix; i64 result; }; monoid_t zero() { return {0, 0, 0, 0}; } monoid_t merge(const monoid_t &x, const monoid_t &y) { monoid_t r; r.total = x.total + y.total; r.max_prefix = max(x.max_prefix, x.total + y.max_prefix); r.max_suffix = max(y.max_suffix, y.total + x.max_suffix); r.result = max(max( max(r.total, x.max_prefix + y.max_suffix), max(x.total + y.result, x.result + y.total) ), 0LL); return r; } monoid_t inject(i64 value) { monoid_t r; r.total = value; r.max_prefix = max(0LL, value); r.max_suffix = max(0LL, value); r.result = max(0LL, value); return r; } void send(int target, const monoid_t& m) { PutLL(target, m.total); PutLL(target, m.max_prefix); PutLL(target, m.max_suffix); PutLL(target, m.result); Send(target); } monoid_t receive(int source) { monoid_t r; Receive(source); r.total = GetLL(source); r.max_prefix = GetLL(source); r.max_suffix = GetLL(source); r.result = GetLL(source); return r; } int main() { int p = MyNodeId(); int pn = NumberOfNodes(); i64 lower = ((GetN() - 1) * p) / pn + (p == 0 ? 0 : 1); i64 upper = ((GetN() - 1) * (p + 1)) / pn; monoid_t m = zero(); for (i64 i = lower; i <= upper; ++i) { m = merge(m, inject(GetTaste(i))); } if (p == 0) { for (int i = 1; i < pn; ++i) { m = merge(m, receive(i)); } printf("%lld\n", m.result); } else { send(0, m); } return 0; }
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 | #include <cstdio> #include <algorithm> #include "message.h" #include "kanapka.h" using namespace std; typedef long long i64; struct monoid_t { i64 total; i64 max_prefix; i64 max_suffix; i64 result; }; monoid_t zero() { return {0, 0, 0, 0}; } monoid_t merge(const monoid_t &x, const monoid_t &y) { monoid_t r; r.total = x.total + y.total; r.max_prefix = max(x.max_prefix, x.total + y.max_prefix); r.max_suffix = max(y.max_suffix, y.total + x.max_suffix); r.result = max(max( max(r.total, x.max_prefix + y.max_suffix), max(x.total + y.result, x.result + y.total) ), 0LL); return r; } monoid_t inject(i64 value) { monoid_t r; r.total = value; r.max_prefix = max(0LL, value); r.max_suffix = max(0LL, value); r.result = max(0LL, value); return r; } void send(int target, const monoid_t& m) { PutLL(target, m.total); PutLL(target, m.max_prefix); PutLL(target, m.max_suffix); PutLL(target, m.result); Send(target); } monoid_t receive(int source) { monoid_t r; Receive(source); r.total = GetLL(source); r.max_prefix = GetLL(source); r.max_suffix = GetLL(source); r.result = GetLL(source); return r; } int main() { int p = MyNodeId(); int pn = NumberOfNodes(); i64 lower = ((GetN() - 1) * p) / pn + (p == 0 ? 0 : 1); i64 upper = ((GetN() - 1) * (p + 1)) / pn; monoid_t m = zero(); for (i64 i = lower; i <= upper; ++i) { m = merge(m, inject(GetTaste(i))); } if (p == 0) { for (int i = 1; i < pn; ++i) { m = merge(m, receive(i)); } printf("%lld\n", m.result); } else { send(0, m); } return 0; } |