#include "kanapka.h" #include "message.h" #include <iostream> #include <algorithm> #include <cmath> using namespace std; long long Left_max[105]; long long Right_max[105]; long long Sum[105]; long long inf = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL; int main() { ios_base::sync_with_stdio(0); if (MyNodeId() == 0) { long long left_max = 0, right_max = 0, sum = 0; PutLL(1, 0LL); PutLL(1, 0LL); for (int i = 1; i < NumberOfNodes(); i++) { Receive(i); Left_max[i] = GetLL(i); Right_max[i] = GetLL(i); Sum[i] = GetLL(i); left_max = max(left_max, sum + Left_max[i]); sum += Sum[i]; if (i + 1 < NumberOfNodes()) { PutLL(i + 1, left_max); PutLL(i + 1, sum); } } sum = 0; PutLL(NumberOfNodes() - 1, 0LL); PutLL(NumberOfNodes() - 1, 0LL); Send(NumberOfNodes() - 1); for (int i = NumberOfNodes() - 1; i > 0; i--) { right_max = max(right_max, sum + Right_max[i]); sum += Sum[i]; if (i - 1 >= 1) { PutLL(i - 1, right_max); PutLL(i - 1, sum); Send(i - 1); } } long long ans = 0; for (int i = 1; i < NumberOfNodes(); i++) { Receive(i); ans = max(ans, GetLL(i)); } cout << ans << "\n"; //if (left_i < right_i) cout << left_max + right_max << "\n"; //else cout << sum << "\n"; } else { int n = ceil(1.0 * GetN() / (NumberOfNodes() - 1)); long long left_max = 0, right_max = 0, sum = 0; for (int i = (MyNodeId() - 1) * n; i < MyNodeId() * n and i < GetN(); i++) { //cout << i << " "; sum += GetTaste(i); left_max = max(left_max, sum); } sum = 0; for (int i = min(MyNodeId() * n, (int)GetN()) - 1; i >= (MyNodeId() - 1) * n; i--) { sum += GetTaste(i); right_max = max(right_max, sum); } PutLL(0, left_max); PutLL(0, right_max); PutLL(0, sum); Send(0); Receive(0); left_max = GetLL(0); long long left_sum = GetLL(0); right_max = GetLL(0); long long right_sum = GetLL(0); long long sum2 = sum; long long Sum = sum; sum = 0; long long mx = 0; //cout << left_max << " " << left_sum << " " << right_max << " " << right_sum << "\n"; for (int i = (MyNodeId() - 1) * n; i < MyNodeId() * n and i < GetN(); i++) { mx = max(mx, left_max + sum2 + right_sum); //cout << left_max << " " << sum2 << "\n"; //cout << i << "\n"; sum2 -= GetTaste(i); sum += GetTaste(i); left_max = max(left_max, left_sum + sum); } sum = 0, sum2 = Sum; for (int i = min(MyNodeId() * n, (int)GetN()) - 1; i >= (MyNodeId() - 1) * n; i--) { mx = max(mx, right_max + sum2 + left_sum); //cout << right_max << " " << sum2 << "\n"; sum2 -= GetTaste(i); sum += GetTaste(i); right_max = max(right_max, right_sum + sum); } PutLL(0, mx); Send(0); } 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 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 | #include "kanapka.h" #include "message.h" #include <iostream> #include <algorithm> #include <cmath> using namespace std; long long Left_max[105]; long long Right_max[105]; long long Sum[105]; long long inf = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL; int main() { ios_base::sync_with_stdio(0); if (MyNodeId() == 0) { long long left_max = 0, right_max = 0, sum = 0; PutLL(1, 0LL); PutLL(1, 0LL); for (int i = 1; i < NumberOfNodes(); i++) { Receive(i); Left_max[i] = GetLL(i); Right_max[i] = GetLL(i); Sum[i] = GetLL(i); left_max = max(left_max, sum + Left_max[i]); sum += Sum[i]; if (i + 1 < NumberOfNodes()) { PutLL(i + 1, left_max); PutLL(i + 1, sum); } } sum = 0; PutLL(NumberOfNodes() - 1, 0LL); PutLL(NumberOfNodes() - 1, 0LL); Send(NumberOfNodes() - 1); for (int i = NumberOfNodes() - 1; i > 0; i--) { right_max = max(right_max, sum + Right_max[i]); sum += Sum[i]; if (i - 1 >= 1) { PutLL(i - 1, right_max); PutLL(i - 1, sum); Send(i - 1); } } long long ans = 0; for (int i = 1; i < NumberOfNodes(); i++) { Receive(i); ans = max(ans, GetLL(i)); } cout << ans << "\n"; //if (left_i < right_i) cout << left_max + right_max << "\n"; //else cout << sum << "\n"; } else { int n = ceil(1.0 * GetN() / (NumberOfNodes() - 1)); long long left_max = 0, right_max = 0, sum = 0; for (int i = (MyNodeId() - 1) * n; i < MyNodeId() * n and i < GetN(); i++) { //cout << i << " "; sum += GetTaste(i); left_max = max(left_max, sum); } sum = 0; for (int i = min(MyNodeId() * n, (int)GetN()) - 1; i >= (MyNodeId() - 1) * n; i--) { sum += GetTaste(i); right_max = max(right_max, sum); } PutLL(0, left_max); PutLL(0, right_max); PutLL(0, sum); Send(0); Receive(0); left_max = GetLL(0); long long left_sum = GetLL(0); right_max = GetLL(0); long long right_sum = GetLL(0); long long sum2 = sum; long long Sum = sum; sum = 0; long long mx = 0; //cout << left_max << " " << left_sum << " " << right_max << " " << right_sum << "\n"; for (int i = (MyNodeId() - 1) * n; i < MyNodeId() * n and i < GetN(); i++) { mx = max(mx, left_max + sum2 + right_sum); //cout << left_max << " " << sum2 << "\n"; //cout << i << "\n"; sum2 -= GetTaste(i); sum += GetTaste(i); left_max = max(left_max, left_sum + sum); } sum = 0, sum2 = Sum; for (int i = min(MyNodeId() * n, (int)GetN()) - 1; i >= (MyNodeId() - 1) * n; i--) { mx = max(mx, right_max + sum2 + left_sum); //cout << right_max << " " << sum2 << "\n"; sum2 -= GetTaste(i); sum += GetTaste(i); right_max = max(right_max, right_sum + sum); } PutLL(0, mx); Send(0); } return 0; } |