#include "kanapka.h" #include "message.h" #include <string> #include <algorithm> #include <iostream> using namespace std; void calculate(long long fromIdx, long long toIdx) { long long sum; long long leftMax; long long rightMax; if (toIdx - fromIdx == 1) { leftMax = 0; sum = GetTaste(fromIdx); rightMax = sum; } else { leftMax = 0; sum = 0; rightMax = 0; long long rightMaxIdx = -1; for (int i = fromIdx; i < toIdx; i++) { long long val = GetTaste(i); sum += val; long long tmpLeftSum = max(sum, 0LL); if (sum > leftMax || i == fromIdx) { if (rightMaxIdx > i) { leftMax = tmpLeftSum; } else { long long tmpRightSum = 0; long long maxTmpRightSum; for (long long j = toIdx - 1; j > i; j--) { tmpRightSum += GetTaste(j); maxTmpRightSum = max(tmpRightSum, 0LL); if (maxTmpRightSum + tmpLeftSum > rightMax + leftMax) { rightMax = maxTmpRightSum; rightMaxIdx = j; leftMax = tmpLeftSum; } } } } } } int receiver = NumberOfNodes() - 1; PutLL(receiver, leftMax); PutLL(receiver, sum); PutLL(receiver, rightMax); Send(receiver); } const int MIN_ELEMENTS = 20; int main() { int id = MyNodeId(); int nodes = NumberOfNodes(); int workers = nodes; long long N = GetN(); long long size = N / nodes; if (size < MIN_ELEMENTS) { workers = (N / MIN_ELEMENTS) + (N % MIN_ELEMENTS == 0 ? 0 : 1); size = (N / workers) + (N % workers == 0 ? 0 : 1);; } if (id < workers - 1) { calculate(id * size, id * size + size); } else if (id == workers - 1) { calculate(id * size, N); } // Last node is receiver if (id == nodes - 1) { long long lefts[workers]; long long totals[workers]; long long rights[workers]; for (int i = 0; i < workers; i++) { int sender = Receive(-1); lefts[sender] = GetLL(sender); totals[sender] = GetLL(sender); rights[sender] = GetLL(sender); } if (workers == 1) { cout << max(0ll, max(totals[0], lefts[0] + rights[0])) << endl; return 0; } long long leftSum[workers + 1]; long long leftTotalSum[workers + 1]; long long rightSum[workers + 2]; long long rightTotalSum[workers + 2]; leftSum[0] = 0; leftTotalSum[0] = 0; rightSum[0] = 0; rightSum[workers + 1] = 0; rightTotalSum[0] = 0; rightTotalSum[workers + 1] = 0; for (long long i = 0; i < workers; i++) { leftSum[i + 1] = leftTotalSum[i] + lefts[i]; leftTotalSum[i + 1] = leftTotalSum[i] + totals[i]; } for (long long i = workers; i > 0; i--) { rightSum[i] = rightTotalSum[i + 1] + rights[i - 1]; rightTotalSum[i] = rightTotalSum[i + 1] + totals[i - 1]; } long long leftMax = 0; long long rightMax = 0; long long totalMax = rightTotalSum[1]; for (long long i = 1; i < workers + 1; i++) { if (leftSum[i] > leftMax) { long long right = 0; for (long long j = i; j <= workers + 1; j++) { if (rightSum[j] > right) { right = rightSum[j]; if (leftSum[i] + right > totalMax) { leftMax = leftSum[i]; totalMax = leftMax + right; rightMax = right; } } } } } cout << max(0ll, max(totalMax, leftMax + rightMax)) << 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 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 130 | #include "kanapka.h" #include "message.h" #include <string> #include <algorithm> #include <iostream> using namespace std; void calculate(long long fromIdx, long long toIdx) { long long sum; long long leftMax; long long rightMax; if (toIdx - fromIdx == 1) { leftMax = 0; sum = GetTaste(fromIdx); rightMax = sum; } else { leftMax = 0; sum = 0; rightMax = 0; long long rightMaxIdx = -1; for (int i = fromIdx; i < toIdx; i++) { long long val = GetTaste(i); sum += val; long long tmpLeftSum = max(sum, 0LL); if (sum > leftMax || i == fromIdx) { if (rightMaxIdx > i) { leftMax = tmpLeftSum; } else { long long tmpRightSum = 0; long long maxTmpRightSum; for (long long j = toIdx - 1; j > i; j--) { tmpRightSum += GetTaste(j); maxTmpRightSum = max(tmpRightSum, 0LL); if (maxTmpRightSum + tmpLeftSum > rightMax + leftMax) { rightMax = maxTmpRightSum; rightMaxIdx = j; leftMax = tmpLeftSum; } } } } } } int receiver = NumberOfNodes() - 1; PutLL(receiver, leftMax); PutLL(receiver, sum); PutLL(receiver, rightMax); Send(receiver); } const int MIN_ELEMENTS = 20; int main() { int id = MyNodeId(); int nodes = NumberOfNodes(); int workers = nodes; long long N = GetN(); long long size = N / nodes; if (size < MIN_ELEMENTS) { workers = (N / MIN_ELEMENTS) + (N % MIN_ELEMENTS == 0 ? 0 : 1); size = (N / workers) + (N % workers == 0 ? 0 : 1);; } if (id < workers - 1) { calculate(id * size, id * size + size); } else if (id == workers - 1) { calculate(id * size, N); } // Last node is receiver if (id == nodes - 1) { long long lefts[workers]; long long totals[workers]; long long rights[workers]; for (int i = 0; i < workers; i++) { int sender = Receive(-1); lefts[sender] = GetLL(sender); totals[sender] = GetLL(sender); rights[sender] = GetLL(sender); } if (workers == 1) { cout << max(0ll, max(totals[0], lefts[0] + rights[0])) << endl; return 0; } long long leftSum[workers + 1]; long long leftTotalSum[workers + 1]; long long rightSum[workers + 2]; long long rightTotalSum[workers + 2]; leftSum[0] = 0; leftTotalSum[0] = 0; rightSum[0] = 0; rightSum[workers + 1] = 0; rightTotalSum[0] = 0; rightTotalSum[workers + 1] = 0; for (long long i = 0; i < workers; i++) { leftSum[i + 1] = leftTotalSum[i] + lefts[i]; leftTotalSum[i + 1] = leftTotalSum[i] + totals[i]; } for (long long i = workers; i > 0; i--) { rightSum[i] = rightTotalSum[i + 1] + rights[i - 1]; rightTotalSum[i] = rightTotalSum[i + 1] + totals[i - 1]; } long long leftMax = 0; long long rightMax = 0; long long totalMax = rightTotalSum[1]; for (long long i = 1; i < workers + 1; i++) { if (leftSum[i] > leftMax) { long long right = 0; for (long long j = i; j <= workers + 1; j++) { if (rightSum[j] > right) { right = rightSum[j]; if (leftSum[i] + right > totalMax) { leftMax = leftSum[i]; totalMax = leftMax + right; rightMax = right; } } } } } cout << max(0ll, max(totalMax, leftMax + rightMax)) << endl; } return 0; } |