#include "kanapka.h" #include "message.h" #include <algorithm> #include <iostream> using namespace std; int main() { long long n = GetN(); int nodes = NumberOfNodes(); int node = MyNodeId(); long long block_size = (n + nodes - 1) / nodes; long long beg = min(n, block_size * node); long long end = min(n, beg + block_size); int size = end - beg; long long pref = 0, suf = 0, sum = 0, prefsuf = 0; long long cur = 0; long long taste[size]; long long best_pref[size]; for (long long i=beg; i<end; i++) taste[i-beg] = GetTaste(i); for (int i=0; i<size; i++) { cur += taste[i]; best_pref[i] = max(cur, (i ? best_pref[i-1] : 0)); } pref = (size ? best_pref[size-1] : 0); sum = cur; cur = 0; for (int i=size-1; i>=0; i--) { cur += taste[i]; prefsuf = max(prefsuf, cur + (i ? best_pref[i-1] : 0)); suf = max(suf, cur); } if (node) { PutLL(0, sum); PutLL(0, pref); PutLL(0, suf); PutLL(0, prefsuf); Send(0); } else { long long sums[nodes], prefs[nodes], sufs[nodes], prefsufs[nodes]; sums[0] = sum; prefs[0] = pref; sufs[0] = suf; prefsufs[0] = prefsuf; for (int i=1; i<nodes; i++) { int x = Receive(-1); sums[x] = GetLL(x); prefs[x] = GetLL(x); sufs[x] = GetLL(x); prefsufs[x] = GetLL(x); } long long res = 0; long long total = 0; for (int i=0; i<nodes; i++) total += sums[i]; res = max(res, total); long long best_pref[nodes], cur = 0, prefsum[nodes], sufsum[nodes]; for (int i=0; i<nodes; i++) prefsum[i] = (i ? prefsum[i-1] : 0) + sums[i]; for (int i=nodes-1; i>=0; i--) sufsum[i] = total - (i ? prefsum[i-1] : 0); for (int i=0; i<nodes; i++) { best_pref[i] = max(cur + prefs[i], (i ? best_pref[i-1] : 0)); cur += sums[i]; } cur = 0; for (int i=nodes-1; i>=0; i--) { res = max(res, cur + sufs[i] + (i ? best_pref[i-1] : 0)); cur += sums[i]; } for (int i=0; i<nodes; i++) res = max(res, (i ? prefsum[i-1] : 0) + (i < nodes-1 ? sufsum[i+1] : 0) + prefsufs[i]); cout << res << "\n"; } 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 | #include "kanapka.h" #include "message.h" #include <algorithm> #include <iostream> using namespace std; int main() { long long n = GetN(); int nodes = NumberOfNodes(); int node = MyNodeId(); long long block_size = (n + nodes - 1) / nodes; long long beg = min(n, block_size * node); long long end = min(n, beg + block_size); int size = end - beg; long long pref = 0, suf = 0, sum = 0, prefsuf = 0; long long cur = 0; long long taste[size]; long long best_pref[size]; for (long long i=beg; i<end; i++) taste[i-beg] = GetTaste(i); for (int i=0; i<size; i++) { cur += taste[i]; best_pref[i] = max(cur, (i ? best_pref[i-1] : 0)); } pref = (size ? best_pref[size-1] : 0); sum = cur; cur = 0; for (int i=size-1; i>=0; i--) { cur += taste[i]; prefsuf = max(prefsuf, cur + (i ? best_pref[i-1] : 0)); suf = max(suf, cur); } if (node) { PutLL(0, sum); PutLL(0, pref); PutLL(0, suf); PutLL(0, prefsuf); Send(0); } else { long long sums[nodes], prefs[nodes], sufs[nodes], prefsufs[nodes]; sums[0] = sum; prefs[0] = pref; sufs[0] = suf; prefsufs[0] = prefsuf; for (int i=1; i<nodes; i++) { int x = Receive(-1); sums[x] = GetLL(x); prefs[x] = GetLL(x); sufs[x] = GetLL(x); prefsufs[x] = GetLL(x); } long long res = 0; long long total = 0; for (int i=0; i<nodes; i++) total += sums[i]; res = max(res, total); long long best_pref[nodes], cur = 0, prefsum[nodes], sufsum[nodes]; for (int i=0; i<nodes; i++) prefsum[i] = (i ? prefsum[i-1] : 0) + sums[i]; for (int i=nodes-1; i>=0; i--) sufsum[i] = total - (i ? prefsum[i-1] : 0); for (int i=0; i<nodes; i++) { best_pref[i] = max(cur + prefs[i], (i ? best_pref[i-1] : 0)); cur += sums[i]; } cur = 0; for (int i=nodes-1; i>=0; i--) { res = max(res, cur + sufs[i] + (i ? best_pref[i-1] : 0)); cur += sums[i]; } for (int i=0; i<nodes; i++) res = max(res, (i ? prefsum[i-1] : 0) + (i < nodes-1 ? sufsum[i+1] : 0) + prefsufs[i]); cout << res << "\n"; } return 0; } |