#include <algorithm> #include <iostream> using namespace std; #include "message.h" #include "kanapka.h" typedef long long ll; const ll SMALL = 1000; // threshold to run on multiple instances int my_id, nodes; ll N, L, R; ll total(ll b, ll e) { ll res = 0; for (ll i = b; i < e; i++) res += GetTaste(i); return res; } ll worst(ll b, ll e) { ll res = 0; ll w = 0; for (ll i = b; i < e; i++) { w += GetTaste(i); res = min(res, w); w = min(0LL, w); } return res; } ll worst_from_left(ll b, ll e) { ll res = 0; ll w = 0; for (ll i = b; i < e; i++) { w += GetTaste(i); res = min(res, w); } return res; } ll worst_from_right(ll b, ll e) { ll res = 0; ll w = 0; for (ll i = e-1; i >= b; i--) { w += GetTaste(i); res = min(res, w); } return res; } ll solve() { ll t[nodes], ct[nodes], wfr[nodes], wfl[nodes]; ll ww = 0; for (int i = 0; i < nodes; i++) { Receive(i); t[i] = GetLL(i); ww = min(ww, GetLL(i)); wfr[i] = GetLL(i); wfl[i] = GetLL(i); } ct[0] = t[0]; for (int i = 1; i < nodes; i++) { ct[i] = ct[i-1] + t[i]; } ll tt = ct[nodes-1]; ll ws = 0; for (int i = 0; i < nodes-1; i++) { for (int j = i+1; j < nodes; j++) { ll wb = wfr[i] + wfl[j] + (ct[j-1] - ct[i]); ws = min(ws, wb); } } cerr << "total=" << tt << " worst(in_part)=" << ww << " worst(split)=" << ws << '\n'; return tt - min(ww, ws); } int main() { my_id = MyNodeId(); nodes = NumberOfNodes(); N = GetN(); if (N < SMALL) { if (my_id > 0) return 0; ll t = total(0, N), w = worst(0, N); cerr << "total=" << t << " worst(in_part)=" << w << '\n'; cout << (t-w) << '\n'; return 0; } ll size = N / nodes; L = my_id * size; R = L + size; if (my_id + 1 == nodes) R = N; cerr << "[" << L << ", " << R << ")\n"; PutLL(0, total(L, R)); PutLL(0, worst(L, R)); PutLL(0, worst_from_right(L, R)); PutLL(0, worst_from_left(L, R)); Send(0); if (my_id > 0) return 0; cout << solve() << '\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 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 | #include <algorithm> #include <iostream> using namespace std; #include "message.h" #include "kanapka.h" typedef long long ll; const ll SMALL = 1000; // threshold to run on multiple instances int my_id, nodes; ll N, L, R; ll total(ll b, ll e) { ll res = 0; for (ll i = b; i < e; i++) res += GetTaste(i); return res; } ll worst(ll b, ll e) { ll res = 0; ll w = 0; for (ll i = b; i < e; i++) { w += GetTaste(i); res = min(res, w); w = min(0LL, w); } return res; } ll worst_from_left(ll b, ll e) { ll res = 0; ll w = 0; for (ll i = b; i < e; i++) { w += GetTaste(i); res = min(res, w); } return res; } ll worst_from_right(ll b, ll e) { ll res = 0; ll w = 0; for (ll i = e-1; i >= b; i--) { w += GetTaste(i); res = min(res, w); } return res; } ll solve() { ll t[nodes], ct[nodes], wfr[nodes], wfl[nodes]; ll ww = 0; for (int i = 0; i < nodes; i++) { Receive(i); t[i] = GetLL(i); ww = min(ww, GetLL(i)); wfr[i] = GetLL(i); wfl[i] = GetLL(i); } ct[0] = t[0]; for (int i = 1; i < nodes; i++) { ct[i] = ct[i-1] + t[i]; } ll tt = ct[nodes-1]; ll ws = 0; for (int i = 0; i < nodes-1; i++) { for (int j = i+1; j < nodes; j++) { ll wb = wfr[i] + wfl[j] + (ct[j-1] - ct[i]); ws = min(ws, wb); } } cerr << "total=" << tt << " worst(in_part)=" << ww << " worst(split)=" << ws << '\n'; return tt - min(ww, ws); } int main() { my_id = MyNodeId(); nodes = NumberOfNodes(); N = GetN(); if (N < SMALL) { if (my_id > 0) return 0; ll t = total(0, N), w = worst(0, N); cerr << "total=" << t << " worst(in_part)=" << w << '\n'; cout << (t-w) << '\n'; return 0; } ll size = N / nodes; L = my_id * size; R = L + size; if (my_id + 1 == nodes) R = N; cerr << "[" << L << ", " << R << ")\n"; PutLL(0, total(L, R)); PutLL(0, worst(L, R)); PutLL(0, worst_from_right(L, R)); PutLL(0, worst_from_left(L, R)); Send(0); if (my_id > 0) return 0; cout << solve() << '\n'; return 0; } |