#include "message.h" #include "kanapka.h" #include <iostream> #include <vector> #include <numeric> #include <utility> #define TT long long using namespace std; const TT BEYOND_TASTE = 1000000001; class Table: protected vector<TT> { protected: TT expanded_N; TT N; TT sum; void copy_and_compact() { TT i, j = 0, acc = 0, i_taste; for (i = 0; i < expanded_N; i++) { i_taste = GetTaste(i); if (i_taste * acc >= 0) { acc += i_taste; } else { (*this)[j++] = acc; acc = i_taste; } } (*this)[j++] = acc; N = j; resize(j); } void calculate_sum() { sum = accumulate(begin(), end(), 0); } public: using vector<TT>::iterator; Table(TT expanded_N_) : vector<TT>(expanded_N_, 0), expanded_N(expanded_N_) { copy_and_compact(); calculate_sum(); } TT solve(iterator range_begin, iterator range_end) { iterator curr_slice_begin = range_begin; iterator curr; TT worst_taste_found = BEYOND_TASTE; TT curr_taste; for (; curr_slice_begin < range_end; curr_slice_begin++) { curr_taste = 0; for (curr = curr_slice_begin; curr < end(); curr++) { curr_taste += *curr; if (curr_taste < worst_taste_found) { worst_taste_found = curr_taste; } } } TT best_solution_in_range = sum - worst_taste_found; return best_solution_in_range < 0 ? 0 : best_solution_in_range; } pair<iterator, iterator> partition(int partitions_count, int partition_num) { double partition_size = size() / partitions_count; iterator partition_start = begin() + partition_size * partition_num; iterator partition_end = begin() + partition_size * (partition_num + 1); if (partition_num == partitions_count - 1) { partition_end = end(); } return make_pair(partition_start, partition_end); } }; int main(int argc, char** argv) { int nodes = NumberOfNodes(); int node_id = MyNodeId(); int i; Table table(GetN()); Table::iterator range_begin = table.partition(nodes, node_id).first; Table::iterator range_end = table.partition(nodes, node_id).second; TT solution = table.solve(range_begin, range_end); if (node_id > 0) { PutLL(0, solution); Send(0); } else { for (i = 1; i < nodes; i++) { Receive(i); solution = max(solution, GetLL(i)); } cout << solution << 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 | #include "message.h" #include "kanapka.h" #include <iostream> #include <vector> #include <numeric> #include <utility> #define TT long long using namespace std; const TT BEYOND_TASTE = 1000000001; class Table: protected vector<TT> { protected: TT expanded_N; TT N; TT sum; void copy_and_compact() { TT i, j = 0, acc = 0, i_taste; for (i = 0; i < expanded_N; i++) { i_taste = GetTaste(i); if (i_taste * acc >= 0) { acc += i_taste; } else { (*this)[j++] = acc; acc = i_taste; } } (*this)[j++] = acc; N = j; resize(j); } void calculate_sum() { sum = accumulate(begin(), end(), 0); } public: using vector<TT>::iterator; Table(TT expanded_N_) : vector<TT>(expanded_N_, 0), expanded_N(expanded_N_) { copy_and_compact(); calculate_sum(); } TT solve(iterator range_begin, iterator range_end) { iterator curr_slice_begin = range_begin; iterator curr; TT worst_taste_found = BEYOND_TASTE; TT curr_taste; for (; curr_slice_begin < range_end; curr_slice_begin++) { curr_taste = 0; for (curr = curr_slice_begin; curr < end(); curr++) { curr_taste += *curr; if (curr_taste < worst_taste_found) { worst_taste_found = curr_taste; } } } TT best_solution_in_range = sum - worst_taste_found; return best_solution_in_range < 0 ? 0 : best_solution_in_range; } pair<iterator, iterator> partition(int partitions_count, int partition_num) { double partition_size = size() / partitions_count; iterator partition_start = begin() + partition_size * partition_num; iterator partition_end = begin() + partition_size * (partition_num + 1); if (partition_num == partitions_count - 1) { partition_end = end(); } return make_pair(partition_start, partition_end); } }; int main(int argc, char** argv) { int nodes = NumberOfNodes(); int node_id = MyNodeId(); int i; Table table(GetN()); Table::iterator range_begin = table.partition(nodes, node_id).first; Table::iterator range_end = table.partition(nodes, node_id).second; TT solution = table.solve(range_begin, range_end); if (node_id > 0) { PutLL(0, solution); Send(0); } else { for (i = 1; i < nodes; i++) { Receive(i); solution = max(solution, GetLL(i)); } cout << solution << endl; } return 0; } |