#include <iostream> #include "kanapka.h" #include "message.h" #include <vector> #include <algorithm> #define ll long long using namespace std; ll solve_brut() { ll n = GetN(); vector<ll> A; for(int i=0;i<n;i++) { A.push_back(GetTaste(i)); } vector<ll>best_pref; vector<ll>best_suff; ll cur =0; for(int i=0;i<n;i++) { ll bp = i==0?0:best_pref[i-1]; cur += A[i]; best_pref.push_back(max(cur, bp)); } best_suff.resize(n); cur =0; for(int i=n-1;i>=0;i--) { ll bp = i==n-1?0:best_suff[i+1]; cur += A[i]; best_suff[i] = (max(cur, bp)); } ll res =0; for(int i=0;i<n;i++) { ll left = best_pref[i]; ll right = i==n-1?0:best_suff[i+1]; res = max(res, left+right); } return res; } ll my_from; ll my_to; vector<ll>my_part; ll n; ll myId; ll nodes; void init() { nodes = NumberOfNodes(); n = GetN(); myId = MyNodeId(); if(nodes > n) { nodes = n; } ll per_node = n / nodes; ll rest = n % nodes; int start=0; for(int i=0;i<nodes;i++) { int end = start +per_node; if(i<rest)end++; if(i==myId) { my_from = start; my_to = end; } start = end; } for(ll i = my_from;i<my_to;i++) { my_part.push_back(GetTaste(i)); } // cout << MyNodeId() << "[" << my_from << ","<<my_to << "]"<< endl; } ll my_sum() { ll res =0; for(auto p = my_part.begin();p!=my_part.end();p++) res += *p; return res; } ll solve(ll left_sum, ll left_pref, ll right_sum, ll right_suf) { ll cur = left_sum; ll prev_best = left_pref; vector<ll>best_pref; vector<ll>best_suff; for(auto p = my_part.begin();p!=my_part.end();p++) { ll x = *p; cur += x; prev_best = max(cur, prev_best); best_pref.push_back(prev_best); } ll my_n = my_to - my_from; best_suff.resize(my_n); cur = right_sum; prev_best = right_suf; for(ll i = my_n-1;i>=0;i--) { cur += my_part[i]; prev_best = max(prev_best, cur); best_suff[i] = prev_best; } ll res =0; for(int i=0;i<my_n;i++) { ll left = best_pref[i]; ll right = i==my_n-1?right_suf:best_suff[i+1]; res = max(res, left+right); } return res; } int main() { init(); if(myId>=nodes)return 0; // -------- sum ------------- ll s = my_sum(); ll sum_left =0; ll sum_right =0; if(myId>0) { Receive(myId-1); ll x = GetLL(myId -1); sum_left+=x; } if(myId +1 < nodes) { PutLL(myId + 1, sum_left + s); Send(myId + 1); Receive(myId + 1); ll x = GetLL(myId + 1); sum_right += x; } if(myId > 0) { PutLL(myId - 1, sum_right + s); Send(myId -1); } // ----------- prefix ----------- ll best_pref =0; ll left_pref=0; if (myId > 0) { Receive(myId-1); left_pref = GetLL(myId -1); } ll cur = sum_left; best_pref = left_pref; for(auto p = my_part.begin();p!=my_part.end();p++) { cur += *p; best_pref =max(best_pref, cur); } if(myId + 1 < nodes) { PutLL(myId + 1, best_pref); Send(myId+1); } // ----------- suffix ----------- ll best_suf = 0; ll right_suf=0; if(myId + 1 < nodes) { Receive(myId + 1); right_suf = GetLL(myId+1); } best_suf = right_suf; cur = sum_right; for(auto p = my_part.rbegin();p!=my_part.rend();p++) { cur += *p; best_suf = max(best_suf,cur); } if(myId - 1 >=0) { PutLL(myId - 1, best_suf); Send(myId-1); } //cout << MyNodeId() << ": " << left_pref << ":"<<s << ":"<< right_suf<< endl; // cout << MyNodeId() << ": best pref = " << best_pref <<endl; // cout << MyNodeId() << ": best suf = " << best_suf <<endl; ll best_found = solve(sum_left, left_pref, sum_right, right_suf); //cout << MyNodeId() << ": best found = " << best_found <<endl; if(myId !=0) { PutLL(0, best_found); Send(0); } else { ll res = best_found; for(int i=0;i<nodes -1;i++) { int node = Receive(-1); ll x = GetLL(node); res = max(res, x); } cout << res <<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 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 | #include <iostream> #include "kanapka.h" #include "message.h" #include <vector> #include <algorithm> #define ll long long using namespace std; ll solve_brut() { ll n = GetN(); vector<ll> A; for(int i=0;i<n;i++) { A.push_back(GetTaste(i)); } vector<ll>best_pref; vector<ll>best_suff; ll cur =0; for(int i=0;i<n;i++) { ll bp = i==0?0:best_pref[i-1]; cur += A[i]; best_pref.push_back(max(cur, bp)); } best_suff.resize(n); cur =0; for(int i=n-1;i>=0;i--) { ll bp = i==n-1?0:best_suff[i+1]; cur += A[i]; best_suff[i] = (max(cur, bp)); } ll res =0; for(int i=0;i<n;i++) { ll left = best_pref[i]; ll right = i==n-1?0:best_suff[i+1]; res = max(res, left+right); } return res; } ll my_from; ll my_to; vector<ll>my_part; ll n; ll myId; ll nodes; void init() { nodes = NumberOfNodes(); n = GetN(); myId = MyNodeId(); if(nodes > n) { nodes = n; } ll per_node = n / nodes; ll rest = n % nodes; int start=0; for(int i=0;i<nodes;i++) { int end = start +per_node; if(i<rest)end++; if(i==myId) { my_from = start; my_to = end; } start = end; } for(ll i = my_from;i<my_to;i++) { my_part.push_back(GetTaste(i)); } // cout << MyNodeId() << "[" << my_from << ","<<my_to << "]"<< endl; } ll my_sum() { ll res =0; for(auto p = my_part.begin();p!=my_part.end();p++) res += *p; return res; } ll solve(ll left_sum, ll left_pref, ll right_sum, ll right_suf) { ll cur = left_sum; ll prev_best = left_pref; vector<ll>best_pref; vector<ll>best_suff; for(auto p = my_part.begin();p!=my_part.end();p++) { ll x = *p; cur += x; prev_best = max(cur, prev_best); best_pref.push_back(prev_best); } ll my_n = my_to - my_from; best_suff.resize(my_n); cur = right_sum; prev_best = right_suf; for(ll i = my_n-1;i>=0;i--) { cur += my_part[i]; prev_best = max(prev_best, cur); best_suff[i] = prev_best; } ll res =0; for(int i=0;i<my_n;i++) { ll left = best_pref[i]; ll right = i==my_n-1?right_suf:best_suff[i+1]; res = max(res, left+right); } return res; } int main() { init(); if(myId>=nodes)return 0; // -------- sum ------------- ll s = my_sum(); ll sum_left =0; ll sum_right =0; if(myId>0) { Receive(myId-1); ll x = GetLL(myId -1); sum_left+=x; } if(myId +1 < nodes) { PutLL(myId + 1, sum_left + s); Send(myId + 1); Receive(myId + 1); ll x = GetLL(myId + 1); sum_right += x; } if(myId > 0) { PutLL(myId - 1, sum_right + s); Send(myId -1); } // ----------- prefix ----------- ll best_pref =0; ll left_pref=0; if (myId > 0) { Receive(myId-1); left_pref = GetLL(myId -1); } ll cur = sum_left; best_pref = left_pref; for(auto p = my_part.begin();p!=my_part.end();p++) { cur += *p; best_pref =max(best_pref, cur); } if(myId + 1 < nodes) { PutLL(myId + 1, best_pref); Send(myId+1); } // ----------- suffix ----------- ll best_suf = 0; ll right_suf=0; if(myId + 1 < nodes) { Receive(myId + 1); right_suf = GetLL(myId+1); } best_suf = right_suf; cur = sum_right; for(auto p = my_part.rbegin();p!=my_part.rend();p++) { cur += *p; best_suf = max(best_suf,cur); } if(myId - 1 >=0) { PutLL(myId - 1, best_suf); Send(myId-1); } //cout << MyNodeId() << ": " << left_pref << ":"<<s << ":"<< right_suf<< endl; // cout << MyNodeId() << ": best pref = " << best_pref <<endl; // cout << MyNodeId() << ": best suf = " << best_suf <<endl; ll best_found = solve(sum_left, left_pref, sum_right, right_suf); //cout << MyNodeId() << ": best found = " << best_found <<endl; if(myId !=0) { PutLL(0, best_found); Send(0); } else { ll res = best_found; for(int i=0;i<nodes -1;i++) { int node = Receive(-1); ll x = GetLL(node); res = max(res, x); } cout << res <<endl; } return 0; } |