#include <iostream> #include <vector> #include <algorithm> #include "message.h" #include "kanapka.h" struct Chunk { Chunk(): max_pref(0), max_suf(0), sum(0), max_pref_suf_sum(0) {} Chunk(long long taste): max_pref(std::max(0LL, taste)), max_suf(std::max(0LL, taste)), sum(taste), max_pref_suf_sum(std::max(0LL, taste)) {} long long max_pref; long long max_suf; long long sum; long long max_pref_suf_sum; }; void Send(int target, const Chunk& message) { PutLL(target, message.max_pref); PutLL(target, message.max_suf); PutLL(target, message.sum); PutLL(target, message.max_pref_suf_sum); Send(target); } Chunk ReceiveChunk(int source) { int real = Receive(source); Chunk rv; rv.max_pref = GetLL(real); rv.max_suf = GetLL(real); rv.sum = GetLL(real); rv.max_pref_suf_sum = GetLL(real); return rv; } std::ostream& operator<<(std::ostream& os, const Chunk& msg) { os << "Chunk(" << msg.max_pref << ", " << msg.max_suf << ", " << msg.sum << ", " << msg.max_pref_suf_sum << ")"; return os; } int NODES; Chunk operator+(const Chunk& chunk1, const Chunk& chunk2) { Chunk rv; rv.sum = chunk1.sum + chunk2.sum; rv.max_pref = std::max(chunk1.max_pref, chunk1.sum + chunk2.max_pref); rv.max_suf = std::max(chunk2.max_suf, chunk2.sum + chunk1.max_suf); rv.max_pref_suf_sum = std::max({chunk1.max_pref_suf_sum + chunk2.sum, chunk1.sum + chunk2.max_pref_suf_sum, chunk1.max_pref + chunk2.max_suf}); return rv; } Chunk& operator+=(Chunk& chunk1, const Chunk& chunk2) { chunk1 = chunk1 + chunk2; return chunk1; } Chunk ComputeChunk() { Chunk rv; int start = static_cast<long long>(MyNodeId()) * GetN() / NODES; int end = static_cast<long long>(MyNodeId() + 1) * GetN() / NODES; for (int i = start; i < end; ++i) { rv += Chunk(GetTaste(i)); } return rv; } const int kTastesAtOnce = 1000000; int main() { NODES = std::min((long long) NumberOfNodes(), GetN()); // std::cerr << "node " << MyNodeId() << " out of " << NODES << "\n"; if (MyNodeId() >= NODES) { return 0; } if (MyNodeId() == 0) { Chunk result = ComputeChunk(); for (int i = 1; i < NODES; ++i) { result += ReceiveChunk(i); } std::cout << result.max_pref_suf_sum << "\n"; } else { Send(0, ComputeChunk()); } 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 84 85 86 87 88 89 90 91 | #include <iostream> #include <vector> #include <algorithm> #include "message.h" #include "kanapka.h" struct Chunk { Chunk(): max_pref(0), max_suf(0), sum(0), max_pref_suf_sum(0) {} Chunk(long long taste): max_pref(std::max(0LL, taste)), max_suf(std::max(0LL, taste)), sum(taste), max_pref_suf_sum(std::max(0LL, taste)) {} long long max_pref; long long max_suf; long long sum; long long max_pref_suf_sum; }; void Send(int target, const Chunk& message) { PutLL(target, message.max_pref); PutLL(target, message.max_suf); PutLL(target, message.sum); PutLL(target, message.max_pref_suf_sum); Send(target); } Chunk ReceiveChunk(int source) { int real = Receive(source); Chunk rv; rv.max_pref = GetLL(real); rv.max_suf = GetLL(real); rv.sum = GetLL(real); rv.max_pref_suf_sum = GetLL(real); return rv; } std::ostream& operator<<(std::ostream& os, const Chunk& msg) { os << "Chunk(" << msg.max_pref << ", " << msg.max_suf << ", " << msg.sum << ", " << msg.max_pref_suf_sum << ")"; return os; } int NODES; Chunk operator+(const Chunk& chunk1, const Chunk& chunk2) { Chunk rv; rv.sum = chunk1.sum + chunk2.sum; rv.max_pref = std::max(chunk1.max_pref, chunk1.sum + chunk2.max_pref); rv.max_suf = std::max(chunk2.max_suf, chunk2.sum + chunk1.max_suf); rv.max_pref_suf_sum = std::max({chunk1.max_pref_suf_sum + chunk2.sum, chunk1.sum + chunk2.max_pref_suf_sum, chunk1.max_pref + chunk2.max_suf}); return rv; } Chunk& operator+=(Chunk& chunk1, const Chunk& chunk2) { chunk1 = chunk1 + chunk2; return chunk1; } Chunk ComputeChunk() { Chunk rv; int start = static_cast<long long>(MyNodeId()) * GetN() / NODES; int end = static_cast<long long>(MyNodeId() + 1) * GetN() / NODES; for (int i = start; i < end; ++i) { rv += Chunk(GetTaste(i)); } return rv; } const int kTastesAtOnce = 1000000; int main() { NODES = std::min((long long) NumberOfNodes(), GetN()); // std::cerr << "node " << MyNodeId() << " out of " << NODES << "\n"; if (MyNodeId() >= NODES) { return 0; } if (MyNodeId() == 0) { Chunk result = ComputeChunk(); for (int i = 1; i < NODES; ++i) { result += ReceiveChunk(i); } std::cout << result.max_pref_suf_sum << "\n"; } else { Send(0, ComputeChunk()); } return 0; } |