#include "message.h" #include "kanapka.h" #include <iostream> #include <vector> using namespace std; using LL = long long; int main() { int n = GetN(); int std_chunk_size = n / NumberOfNodes(); int my_chunk_size; if (MyNodeId() == NumberOfNodes() - 1) { my_chunk_size = n - (NumberOfNodes() - 1) * std_chunk_size; } else { my_chunk_size = std_chunk_size; } LL my_sum = 0; LL beg = MyNodeId() * std_chunk_size; for (int i = beg; i < beg + my_chunk_size; ++i) { my_sum += GetTaste(i); } LL pref_sum = 0; LL best_pref = 0, best_suf = 0; LL both = 0; LL suf_sum = my_sum; for (int i = beg; i < beg + my_chunk_size; ++i) { LL taste = GetTaste(i); both = max(both, suf_sum + best_pref); pref_sum += taste; best_pref = max(best_pref, pref_sum); best_suf = max(best_suf, suf_sum); suf_sum -= taste; } both = max(both, best_pref); if (MyNodeId() != 0) { PutLL(0, my_sum); PutLL(0, best_pref); PutLL(0, best_suf); PutLL(0, both); Send(0); return 0; } int M = NumberOfNodes(); vector<LL> sum(M), pref(M), suf(M), prefsuf(M); sum[0] = my_sum; pref[0] = best_pref; suf[0] = best_suf; prefsuf[0] = both; for (int node = 1; node < NumberOfNodes(); ++node) { Receive(node); sum[node] = GetLL(node); pref[node] = GetLL(node); suf[node] = GetLL(node); prefsuf[node] = GetLL(node); } LL sumall = 0; for (int i = 0; i < NumberOfNodes(); ++i) { sumall += sum[i]; } best_pref = 0; LL sum_pref = 0; LL sum_suf = sumall; LL best = 0; for (int i = 0; i < NumberOfNodes(); ++i) { sum_suf -= sum[i]; best = max(best, best_pref + suf[i] + sum_suf); best = max(best, sumall - sum[i] + prefsuf[i]); best_pref = max(best_pref, sum_pref + pref[i]); sum_pref += sum[i]; } cout << best << endl; 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 "message.h" #include "kanapka.h" #include <iostream> #include <vector> using namespace std; using LL = long long; int main() { int n = GetN(); int std_chunk_size = n / NumberOfNodes(); int my_chunk_size; if (MyNodeId() == NumberOfNodes() - 1) { my_chunk_size = n - (NumberOfNodes() - 1) * std_chunk_size; } else { my_chunk_size = std_chunk_size; } LL my_sum = 0; LL beg = MyNodeId() * std_chunk_size; for (int i = beg; i < beg + my_chunk_size; ++i) { my_sum += GetTaste(i); } LL pref_sum = 0; LL best_pref = 0, best_suf = 0; LL both = 0; LL suf_sum = my_sum; for (int i = beg; i < beg + my_chunk_size; ++i) { LL taste = GetTaste(i); both = max(both, suf_sum + best_pref); pref_sum += taste; best_pref = max(best_pref, pref_sum); best_suf = max(best_suf, suf_sum); suf_sum -= taste; } both = max(both, best_pref); if (MyNodeId() != 0) { PutLL(0, my_sum); PutLL(0, best_pref); PutLL(0, best_suf); PutLL(0, both); Send(0); return 0; } int M = NumberOfNodes(); vector<LL> sum(M), pref(M), suf(M), prefsuf(M); sum[0] = my_sum; pref[0] = best_pref; suf[0] = best_suf; prefsuf[0] = both; for (int node = 1; node < NumberOfNodes(); ++node) { Receive(node); sum[node] = GetLL(node); pref[node] = GetLL(node); suf[node] = GetLL(node); prefsuf[node] = GetLL(node); } LL sumall = 0; for (int i = 0; i < NumberOfNodes(); ++i) { sumall += sum[i]; } best_pref = 0; LL sum_pref = 0; LL sum_suf = sumall; LL best = 0; for (int i = 0; i < NumberOfNodes(); ++i) { sum_suf -= sum[i]; best = max(best, best_pref + suf[i] + sum_suf); best = max(best, sumall - sum[i] + prefsuf[i]); best_pref = max(best_pref, sum_pref + pref[i]); sum_pref += sum[i]; } cout << best << endl; return 0; } |