#include <algorithm> #include <iostream> #include <vector> #include "kanapka.h" #include "message.h" typedef long long LL; struct Sammich { LL sum_tastes; //sum of all sectors of this sammich LL bad_taste; //sum of values of not-eat sectors LL bad_left; //sum of not-eat sectors from left LL bad_right; //sum of not-eat sectors from right }; Sammich readSammich(LL i) { LL taste = GetTaste(i); Sammich sammich; sammich.sum_tastes = taste; sammich.bad_taste = sammich.bad_left = sammich.bad_right = std::min(taste, LL(0)); return sammich; } Sammich operator+(const Sammich& left, const Sammich& right) { Sammich sammich; sammich.sum_tastes = left.sum_tastes + right.sum_tastes; sammich.bad_taste = std::min(std::min(left.bad_taste, right.bad_taste), left.bad_right+right.bad_left); sammich.bad_left = std::min(left.bad_left, left.sum_tastes + right.bad_left); sammich.bad_right = std::min(right.bad_right, right.sum_tastes + left.bad_right); return sammich; } Sammich getSammich(LL start, LL end) { Sammich s = readSammich(start); for(LL i=start+1; i<end; i++) { s = s + readSammich(i); } return s; } Sammich receive(LL nodeId) { Receive((int) nodeId); Sammich sammich; sammich.sum_tastes = GetLL(nodeId); sammich.bad_taste = GetLL(nodeId); sammich.bad_left = GetLL(nodeId); sammich.bad_right = GetLL(nodeId); return sammich; } void send(int nodeId, const Sammich& sammich) { PutLL(nodeId, sammich.sum_tastes); PutLL(nodeId, sammich.bad_taste); PutLL(nodeId, sammich.bad_left); PutLL(nodeId, sammich.bad_right); Send(nodeId); } int main(void) { LL nodeId = MyNodeId(); LL numberOfNodes = NumberOfNodes(); LL n = GetN(); numberOfNodes = std::min(n, numberOfNodes); if (nodeId >= numberOfNodes) { return 0; } LL size = n/numberOfNodes; Sammich sammich = getSammich(size*nodeId, size*(nodeId+1)); if (nodeId == 0) { for(int i=1; i<numberOfNodes; i++) { sammich = sammich + receive(i); } } else { send(0, sammich); } std::cout << sammich.sum_tastes - sammich.bad_taste << 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 | #include <algorithm> #include <iostream> #include <vector> #include "kanapka.h" #include "message.h" typedef long long LL; struct Sammich { LL sum_tastes; //sum of all sectors of this sammich LL bad_taste; //sum of values of not-eat sectors LL bad_left; //sum of not-eat sectors from left LL bad_right; //sum of not-eat sectors from right }; Sammich readSammich(LL i) { LL taste = GetTaste(i); Sammich sammich; sammich.sum_tastes = taste; sammich.bad_taste = sammich.bad_left = sammich.bad_right = std::min(taste, LL(0)); return sammich; } Sammich operator+(const Sammich& left, const Sammich& right) { Sammich sammich; sammich.sum_tastes = left.sum_tastes + right.sum_tastes; sammich.bad_taste = std::min(std::min(left.bad_taste, right.bad_taste), left.bad_right+right.bad_left); sammich.bad_left = std::min(left.bad_left, left.sum_tastes + right.bad_left); sammich.bad_right = std::min(right.bad_right, right.sum_tastes + left.bad_right); return sammich; } Sammich getSammich(LL start, LL end) { Sammich s = readSammich(start); for(LL i=start+1; i<end; i++) { s = s + readSammich(i); } return s; } Sammich receive(LL nodeId) { Receive((int) nodeId); Sammich sammich; sammich.sum_tastes = GetLL(nodeId); sammich.bad_taste = GetLL(nodeId); sammich.bad_left = GetLL(nodeId); sammich.bad_right = GetLL(nodeId); return sammich; } void send(int nodeId, const Sammich& sammich) { PutLL(nodeId, sammich.sum_tastes); PutLL(nodeId, sammich.bad_taste); PutLL(nodeId, sammich.bad_left); PutLL(nodeId, sammich.bad_right); Send(nodeId); } int main(void) { LL nodeId = MyNodeId(); LL numberOfNodes = NumberOfNodes(); LL n = GetN(); numberOfNodes = std::min(n, numberOfNodes); if (nodeId >= numberOfNodes) { return 0; } LL size = n/numberOfNodes; Sammich sammich = getSammich(size*nodeId, size*(nodeId+1)); if (nodeId == 0) { for(int i=1; i<numberOfNodes; i++) { sammich = sammich + receive(i); } } else { send(0, sammich); } std::cout << sammich.sum_tastes - sammich.bad_taste << std::endl; return 0; } |