#include "message.h" #include "kanapka.h" #include <iostream> #include <algorithm> int main() { int nodesC = NumberOfNodes(); int nodeID = MyNodeId(); long long N = GetN(); long long beg = int(double(nodeID) / nodesC*N); long long end = int(double(nodeID + 1) / nodesC*N); long long* maxRightDirArray = new long long[end - beg]; long long maxRightDir = 0; long long maxLeftDir = 0; long long max = 0; long long actualSum; actualSum = 0; //idziemy w prawą stronę for (long long i = beg; i < end; ++i){ actualSum += GetTaste(i); maxRightDir = std::max(actualSum, maxRightDir); maxRightDirArray[i - beg] = maxRightDir; } actualSum = 0; max = maxRightDir; //teraz w lewą for (long long i = end - 1; i > beg; --i){ actualSum += GetTaste(i); maxLeftDir = std::max(actualSum, maxLeftDir); max = std::max(max, maxLeftDir + maxRightDirArray[i - 1]); } if (end > beg) actualSum += GetTaste(beg); maxLeftDir = std::max(actualSum, maxLeftDir); max = std::max(max, maxLeftDir); if (nodeID != 0){ PutLL(0, maxRightDir); PutLL(0, maxLeftDir); PutLL(0, max); PutLL(0, actualSum); Send(0); } else { long long* maxRightDirAll = new long long[nodesC]; long long* maxLeftDirAll = new long long[nodesC]; long long* maxAll = new long long[nodesC]; long long* sumAll = new long long[nodesC]; long long* sumRightDir = new long long[nodesC]; maxRightDirAll[0] = maxRightDir; maxLeftDirAll[0] = maxLeftDir; maxAll[0] = max; sumAll[0] = actualSum; for (int i = 1; i < nodesC; ++i){ Receive(i); maxRightDirAll[i] = GetLL(i); maxLeftDirAll[i] = GetLL(i); maxAll[i] = GetLL(i); sumAll[i] = GetLL(i); } actualSum = sumAll[0]; sumRightDir[0] = actualSum; for (int i = 1; i < nodesC; ++i){ maxRightDirAll[i] = std::max(maxRightDirAll[i - 1], actualSum + maxRightDirAll[i]); actualSum += sumAll[i]; sumRightDir[i] = actualSum; } //sprawdzamy wartosc przy zjedzeniu calej kanapki long long int bestResult = actualSum; actualSum = 0; for (int i = nodesC - 1; i > 0; --i){ //jemy calosc z wylaczeniem pewnej czesci znajdujacej sie w tym kawalku bestResult = std::max(bestResult, actualSum + maxAll[i] + sumRightDir[i - 1]); //jemy najlepsza czesc lewej strony tego kawalka, a z prawej strony nie //ruszajac tego kawalka bestResult = std::max(bestResult, actualSum + maxLeftDirAll[i] + maxRightDirAll[i - 1]); actualSum += sumAll[i]; } bestResult = std::max(bestResult, actualSum + maxAll[0]); bestResult = std::max(bestResult, actualSum + maxLeftDirAll[0]); std::cout << bestResult << std::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 | #include "message.h" #include "kanapka.h" #include <iostream> #include <algorithm> int main() { int nodesC = NumberOfNodes(); int nodeID = MyNodeId(); long long N = GetN(); long long beg = int(double(nodeID) / nodesC*N); long long end = int(double(nodeID + 1) / nodesC*N); long long* maxRightDirArray = new long long[end - beg]; long long maxRightDir = 0; long long maxLeftDir = 0; long long max = 0; long long actualSum; actualSum = 0; //idziemy w prawą stronę for (long long i = beg; i < end; ++i){ actualSum += GetTaste(i); maxRightDir = std::max(actualSum, maxRightDir); maxRightDirArray[i - beg] = maxRightDir; } actualSum = 0; max = maxRightDir; //teraz w lewą for (long long i = end - 1; i > beg; --i){ actualSum += GetTaste(i); maxLeftDir = std::max(actualSum, maxLeftDir); max = std::max(max, maxLeftDir + maxRightDirArray[i - 1]); } if (end > beg) actualSum += GetTaste(beg); maxLeftDir = std::max(actualSum, maxLeftDir); max = std::max(max, maxLeftDir); if (nodeID != 0){ PutLL(0, maxRightDir); PutLL(0, maxLeftDir); PutLL(0, max); PutLL(0, actualSum); Send(0); } else { long long* maxRightDirAll = new long long[nodesC]; long long* maxLeftDirAll = new long long[nodesC]; long long* maxAll = new long long[nodesC]; long long* sumAll = new long long[nodesC]; long long* sumRightDir = new long long[nodesC]; maxRightDirAll[0] = maxRightDir; maxLeftDirAll[0] = maxLeftDir; maxAll[0] = max; sumAll[0] = actualSum; for (int i = 1; i < nodesC; ++i){ Receive(i); maxRightDirAll[i] = GetLL(i); maxLeftDirAll[i] = GetLL(i); maxAll[i] = GetLL(i); sumAll[i] = GetLL(i); } actualSum = sumAll[0]; sumRightDir[0] = actualSum; for (int i = 1; i < nodesC; ++i){ maxRightDirAll[i] = std::max(maxRightDirAll[i - 1], actualSum + maxRightDirAll[i]); actualSum += sumAll[i]; sumRightDir[i] = actualSum; } //sprawdzamy wartosc przy zjedzeniu calej kanapki long long int bestResult = actualSum; actualSum = 0; for (int i = nodesC - 1; i > 0; --i){ //jemy calosc z wylaczeniem pewnej czesci znajdujacej sie w tym kawalku bestResult = std::max(bestResult, actualSum + maxAll[i] + sumRightDir[i - 1]); //jemy najlepsza czesc lewej strony tego kawalka, a z prawej strony nie //ruszajac tego kawalka bestResult = std::max(bestResult, actualSum + maxLeftDirAll[i] + maxRightDirAll[i - 1]); actualSum += sumAll[i]; } bestResult = std::max(bestResult, actualSum + maxAll[0]); bestResult = std::max(bestResult, actualSum + maxLeftDirAll[0]); std::cout << bestResult << std::endl; } return 0; } |