#include <cstdio> #include "message.h" #include "kanapka.h" long long magic = 100000; typedef struct { long long max1, max2; long long ptr1, ptr2; long long sum; long long cond1, cond2; } msg; int main() { long long nodes = NumberOfNodes(); long long id = MyNodeId(); long long n = GetN(); long long start = id * n / nodes; long long end = (id + 1) * n / nodes; if (n <= magic) { end = n; } long long max1 = 0; long long current = 0; long long ptr1 = -1; for (long long i = start; i < end; i++) { current += GetTaste(i); if (current >= max1) { max1 = current; ptr1 = i; } } long long sum = current; long long max2 = 0; long long ptr2 = -1; current = 0; for (long long i = end - 1; i >= start; i--) { current += GetTaste(i); if (current >= max2) { max2 = current; ptr2 = i; } } long long cond1 = 0; long long cond2 = 0; if (ptr1 == end - 1) { cond1 = 1; } if (ptr2 == start) { cond2 = 1; } if (id) { PutLL(0, max1); PutLL(0, max2); PutLL(0, ptr1); PutLL(0, ptr2); PutLL(0, sum); PutLL(0, cond1); PutLL(0, cond2); Send(0); } else { msg t[n]; long long all_sum = sum; for (int i = 1; i < nodes; i++) { Receive(i); t[i].cond2 = GetLL(i); t[i].cond1 = GetLL(i); t[i].sum = GetLL(i); t[i].ptr2 = GetLL(i); t[i].ptr1 = GetLL(i); t[i].max2 = GetLL(i); t[i].max1 = GetLL(i); all_sum += sum; } long long all_max1 = max1; long long global_ptr1 = ptr1; if (cond1) { for (int i = 1; i < nodes; i++) { all_max1 += t[i].max1; if (t[i].ptr1 >= 0) { global_ptr1 = t[i].ptr1; } if (!t[i].cond1) { break; } } } long long all_max2 = 0; long long global_ptr2 = -1; for (int i = nodes - 1; i > 0; i--) { all_max2 += t[i].max2; if (t[i].ptr2 >= 0) { global_ptr2 = t[i].ptr2; } if (!t[i].cond2) { break; } } if (global_ptr2 == end) { if (ptr2 >= 0) { all_max2 += max2; global_ptr2 = ptr2; } } long long all_max = 0; if (global_ptr1 >= global_ptr2) { all_max = all_sum; } else { all_max = all_max1 + all_max2; } if (n > magic) { printf("%lld\n", all_max); } else { if (ptr1 >= ptr2) { printf("%lld\n", sum); } else { printf("%lld\n", max1 + max2); } } } }
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 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | #include <cstdio> #include "message.h" #include "kanapka.h" long long magic = 100000; typedef struct { long long max1, max2; long long ptr1, ptr2; long long sum; long long cond1, cond2; } msg; int main() { long long nodes = NumberOfNodes(); long long id = MyNodeId(); long long n = GetN(); long long start = id * n / nodes; long long end = (id + 1) * n / nodes; if (n <= magic) { end = n; } long long max1 = 0; long long current = 0; long long ptr1 = -1; for (long long i = start; i < end; i++) { current += GetTaste(i); if (current >= max1) { max1 = current; ptr1 = i; } } long long sum = current; long long max2 = 0; long long ptr2 = -1; current = 0; for (long long i = end - 1; i >= start; i--) { current += GetTaste(i); if (current >= max2) { max2 = current; ptr2 = i; } } long long cond1 = 0; long long cond2 = 0; if (ptr1 == end - 1) { cond1 = 1; } if (ptr2 == start) { cond2 = 1; } if (id) { PutLL(0, max1); PutLL(0, max2); PutLL(0, ptr1); PutLL(0, ptr2); PutLL(0, sum); PutLL(0, cond1); PutLL(0, cond2); Send(0); } else { msg t[n]; long long all_sum = sum; for (int i = 1; i < nodes; i++) { Receive(i); t[i].cond2 = GetLL(i); t[i].cond1 = GetLL(i); t[i].sum = GetLL(i); t[i].ptr2 = GetLL(i); t[i].ptr1 = GetLL(i); t[i].max2 = GetLL(i); t[i].max1 = GetLL(i); all_sum += sum; } long long all_max1 = max1; long long global_ptr1 = ptr1; if (cond1) { for (int i = 1; i < nodes; i++) { all_max1 += t[i].max1; if (t[i].ptr1 >= 0) { global_ptr1 = t[i].ptr1; } if (!t[i].cond1) { break; } } } long long all_max2 = 0; long long global_ptr2 = -1; for (int i = nodes - 1; i > 0; i--) { all_max2 += t[i].max2; if (t[i].ptr2 >= 0) { global_ptr2 = t[i].ptr2; } if (!t[i].cond2) { break; } } if (global_ptr2 == end) { if (ptr2 >= 0) { all_max2 += max2; global_ptr2 = ptr2; } } long long all_max = 0; if (global_ptr1 >= global_ptr2) { all_max = all_sum; } else { all_max = all_max1 + all_max2; } if (n > magic) { printf("%lld\n", all_max); } else { if (ptr1 >= ptr2) { printf("%lld\n", sum); } else { printf("%lld\n", max1 + max2); } } } } |