#include <algorithm> #include <cstdio> #include "kanapka.h" #include "message.h" struct group { long long int total; long long int left; long long int right; long long int both; group() { total = right = left = both = 0; } group(long long int number) { total = number; right = left = std::max(number, 0LL); both = 0; } group(long long int t, long long int l, long long int r, long long int b) : total(t), left(l), right(r), both(b) {}; void merge(group& other) { long long int tn = total + other.total; long long int ln = std::max(left, total + other.left); long long int rn = std::max(right + other.total, other.right); long long int bn = std::max(both + other.total, std::max(total + other.both, left + other.right)); total = tn; left = ln; right = rn; both = bn; } }; group ProcessRange(long long int start, long long int end) { group result; for (long long int i = start; i < end; ++i) { group current(GetTaste(i)); result.merge(current); } return result; } int main() { long long int n = GetN(); int id = MyNodeId(); int cnt = NumberOfNodes(); group result; if (n > 10 * cnt) { long long int rangeWidth = (n + cnt - 1) / cnt; result = ProcessRange(rangeWidth * id, std::min(n, rangeWidth * (id + 1))); if (id != 0) { PutLL(0, result.total); PutLL(0, result.left); PutLL(0, result.right); PutLL(0, result.both); Send(0); } else { for (int i = 1; i < cnt; ++i) { Receive(i); group resultI(GetLL(i), GetLL(i), GetLL(i), GetLL(i)); result.merge(resultI); } printf("%lld\n", std::max(result.both, std::max(result.left, result.right))); } } else if (id == 0) { result = ProcessRange(0, n); printf("%lld\n", std::max(result.both, std::max(result.left, result.right))); } 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 83 | #include <algorithm> #include <cstdio> #include "kanapka.h" #include "message.h" struct group { long long int total; long long int left; long long int right; long long int both; group() { total = right = left = both = 0; } group(long long int number) { total = number; right = left = std::max(number, 0LL); both = 0; } group(long long int t, long long int l, long long int r, long long int b) : total(t), left(l), right(r), both(b) {}; void merge(group& other) { long long int tn = total + other.total; long long int ln = std::max(left, total + other.left); long long int rn = std::max(right + other.total, other.right); long long int bn = std::max(both + other.total, std::max(total + other.both, left + other.right)); total = tn; left = ln; right = rn; both = bn; } }; group ProcessRange(long long int start, long long int end) { group result; for (long long int i = start; i < end; ++i) { group current(GetTaste(i)); result.merge(current); } return result; } int main() { long long int n = GetN(); int id = MyNodeId(); int cnt = NumberOfNodes(); group result; if (n > 10 * cnt) { long long int rangeWidth = (n + cnt - 1) / cnt; result = ProcessRange(rangeWidth * id, std::min(n, rangeWidth * (id + 1))); if (id != 0) { PutLL(0, result.total); PutLL(0, result.left); PutLL(0, result.right); PutLL(0, result.both); Send(0); } else { for (int i = 1; i < cnt; ++i) { Receive(i); group resultI(GetLL(i), GetLL(i), GetLL(i), GetLL(i)); result.merge(resultI); } printf("%lld\n", std::max(result.both, std::max(result.left, result.right))); } } else if (id == 0) { result = ProcessRange(0, n); printf("%lld\n", std::max(result.both, std::max(result.left, result.right))); } return 0; } |