#include <cstdlib> #include <algorithm> #include "message.h" #include "kanapka.h" using namespace std; typedef long long ll; int id, non; #define MAXNODES 101 ll L[MAXNODES], R[MAXNODES], S[MAXNODES], Min[MAXNODES]; ll itsL, itsR, itsS, itsMin; void CalcLocal(int, int); void CalcAllAndPrint(); void Communicate(); int main() { id = MyNodeId(); non = NumberOfNodes(); int n = GetN(); int nPerNode = n / non + (n%non ? 1 : 0); int begI = id * nPerNode; int endI = min(begI + nPerNode, n); CalcLocal(begI, endI); Communicate(); if(id == 0) CalcAllAndPrint(); return 0; } void CalcLocal(int begI, int endI) { ll currL = 0, currMin = 0; for(int i = begI; i < endI; ++i) { ll t = GetTaste(i); itsS += t; if((currL += t) < itsL) itsL = currL; if((currMin += t) < itsMin) itsMin = currMin; else if(currMin > 0) currMin = 0; } ll currR = 0; for(int i = endI - 1; i >= begI; --i) { ll t = GetTaste(i); if((currR += t) < itsR) itsR = currR; } } void CalcAllAndPrint() { ll minRegion = 0; ll sum = 0; for(int i = 0; i < non; ++i) { if(Min[i] < minRegion) minRegion = Min[i]; sum += S[i]; } ll currMinRegion = R[0]; for(int i = 1; i < non; ++i) { if((currMinRegion += L[i]) < minRegion) minRegion = currMinRegion; currMinRegion = min(currMinRegion - L[i] + S[i], R[i]); } printf("%lld", sum - minRegion); } void Communicate() { if(id == 0) { L[0] = itsL; R[0] = itsR; S[0] = itsS; Min[0] = itsMin; for(int i = 1; i < non; ++i) { int src = Receive(-1); L[src] = GetLL(src); R[src] = GetLL(src); S[src] = GetLL(src); Min[src] = GetLL(src); } } else { PutLL(0, itsL); PutLL(0, itsR); PutLL(0, itsS); PutLL(0, itsMin); Send(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 | #include <cstdlib> #include <algorithm> #include "message.h" #include "kanapka.h" using namespace std; typedef long long ll; int id, non; #define MAXNODES 101 ll L[MAXNODES], R[MAXNODES], S[MAXNODES], Min[MAXNODES]; ll itsL, itsR, itsS, itsMin; void CalcLocal(int, int); void CalcAllAndPrint(); void Communicate(); int main() { id = MyNodeId(); non = NumberOfNodes(); int n = GetN(); int nPerNode = n / non + (n%non ? 1 : 0); int begI = id * nPerNode; int endI = min(begI + nPerNode, n); CalcLocal(begI, endI); Communicate(); if(id == 0) CalcAllAndPrint(); return 0; } void CalcLocal(int begI, int endI) { ll currL = 0, currMin = 0; for(int i = begI; i < endI; ++i) { ll t = GetTaste(i); itsS += t; if((currL += t) < itsL) itsL = currL; if((currMin += t) < itsMin) itsMin = currMin; else if(currMin > 0) currMin = 0; } ll currR = 0; for(int i = endI - 1; i >= begI; --i) { ll t = GetTaste(i); if((currR += t) < itsR) itsR = currR; } } void CalcAllAndPrint() { ll minRegion = 0; ll sum = 0; for(int i = 0; i < non; ++i) { if(Min[i] < minRegion) minRegion = Min[i]; sum += S[i]; } ll currMinRegion = R[0]; for(int i = 1; i < non; ++i) { if((currMinRegion += L[i]) < minRegion) minRegion = currMinRegion; currMinRegion = min(currMinRegion - L[i] + S[i], R[i]); } printf("%lld", sum - minRegion); } void Communicate() { if(id == 0) { L[0] = itsL; R[0] = itsR; S[0] = itsS; Min[0] = itsMin; for(int i = 1; i < non; ++i) { int src = Receive(-1); L[src] = GetLL(src); R[src] = GetLL(src); S[src] = GetLL(src); Min[src] = GetLL(src); } } else { PutLL(0, itsL); PutLL(0, itsR); PutLL(0, itsS); PutLL(0, itsMin); Send(0); } } |