#include "kanapka.h" #include "message.h" #include <array> #include <vector> #include <cmath> #include<algorithm> #include <iostream> enum : size_t { begin = 0, end = 1, entire = 2, uppermost = 3 }; typedef long long taste_numeral; typedef long long taste; typedef std::array<taste, 4> block; inline bool cmp(const block& a, const block& b) { return a[uppermost] < b[uppermost]; } block local_solve(const taste_numeral p, const taste_numeral q) { //[p;q) block local_result{{0, 0, 0, 0}}; taste begin_sum = 0, worst_sum = 0; for(auto i = p; i < q; ++i) { const taste actual = GetTaste(i); begin_sum += actual; worst_sum += actual; worst_sum = std::min(0LL, worst_sum); local_result[begin] = std::min(local_result[begin], begin_sum); local_result[uppermost] = std::min(local_result[uppermost], worst_sum); } local_result[entire] = begin_sum; taste& end_sum = begin_sum; end_sum = 0; for(auto i = q - 1; i >= p; --i) { end_sum += GetTaste(i); local_result[end] = std::min(local_result[end], end_sum); } return local_result; } int main() { const int nodes_number = NumberOfNodes(), myid = MyNodeId(); const taste_numeral data_size = GetN(); if(data_size < 500000) { if(myid != 0) { return 0; } const block local_result = local_solve(0, data_size); std::cout << local_result[entire] - local_result[uppermost]; return 0; } const taste_numeral interval = data_size/nodes_number; const taste_numeral p = myid * interval; const taste_numeral q = (nodes_number == myid + 1) ? data_size : (myid+1) * interval; const block local_result = local_solve(p, q); if(myid != 0) { for(const auto x : local_result) { PutLL(0, x); } Send(0); return 0; } std::vector<block> results(nodes_number); results[0] = std::move(local_result); for(int i = 1; i < nodes_number; ++i) { const int source = Receive(-1); for(auto& x : results[source]) { x = GetLL(source); } } taste worst_answer = (*std::min_element(std::begin(results), std::end(results), cmp))[uppermost]; for(auto it = std::begin(results); it != std::end(results); ++it) { taste temp = (*it)[end]; for(auto it2 = it+1; it2 != std::end(results); ++it2) { worst_answer = std::min(worst_answer, temp + (*it2)[begin]); temp += (*it2)[entire]; } } taste whole_sum = 0; for(const auto& x : results) { whole_sum += x[entire]; } std::cout << whole_sum - worst_answer << '\n'; }
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 | #include "kanapka.h" #include "message.h" #include <array> #include <vector> #include <cmath> #include<algorithm> #include <iostream> enum : size_t { begin = 0, end = 1, entire = 2, uppermost = 3 }; typedef long long taste_numeral; typedef long long taste; typedef std::array<taste, 4> block; inline bool cmp(const block& a, const block& b) { return a[uppermost] < b[uppermost]; } block local_solve(const taste_numeral p, const taste_numeral q) { //[p;q) block local_result{{0, 0, 0, 0}}; taste begin_sum = 0, worst_sum = 0; for(auto i = p; i < q; ++i) { const taste actual = GetTaste(i); begin_sum += actual; worst_sum += actual; worst_sum = std::min(0LL, worst_sum); local_result[begin] = std::min(local_result[begin], begin_sum); local_result[uppermost] = std::min(local_result[uppermost], worst_sum); } local_result[entire] = begin_sum; taste& end_sum = begin_sum; end_sum = 0; for(auto i = q - 1; i >= p; --i) { end_sum += GetTaste(i); local_result[end] = std::min(local_result[end], end_sum); } return local_result; } int main() { const int nodes_number = NumberOfNodes(), myid = MyNodeId(); const taste_numeral data_size = GetN(); if(data_size < 500000) { if(myid != 0) { return 0; } const block local_result = local_solve(0, data_size); std::cout << local_result[entire] - local_result[uppermost]; return 0; } const taste_numeral interval = data_size/nodes_number; const taste_numeral p = myid * interval; const taste_numeral q = (nodes_number == myid + 1) ? data_size : (myid+1) * interval; const block local_result = local_solve(p, q); if(myid != 0) { for(const auto x : local_result) { PutLL(0, x); } Send(0); return 0; } std::vector<block> results(nodes_number); results[0] = std::move(local_result); for(int i = 1; i < nodes_number; ++i) { const int source = Receive(-1); for(auto& x : results[source]) { x = GetLL(source); } } taste worst_answer = (*std::min_element(std::begin(results), std::end(results), cmp))[uppermost]; for(auto it = std::begin(results); it != std::end(results); ++it) { taste temp = (*it)[end]; for(auto it2 = it+1; it2 != std::end(results); ++it2) { worst_answer = std::min(worst_answer, temp + (*it2)[begin]); temp += (*it2)[entire]; } } taste whole_sum = 0; for(const auto& x : results) { whole_sum += x[entire]; } std::cout << whole_sum - worst_answer << '\n'; } |