#include <iostream> #include <set> #include <vector> #include <algorithm> using namespace std; class City { public: int pos = 0; int value = 0; long long int left = 0; long long int right = 0; friend std::ostream& operator<<(std::ostream& os, const City& obj); }; std::ostream& operator<<(std::ostream& os, const City& obj) { return os << "City(" << obj.pos << "," << obj.value << "," << obj.left << "," << obj.right << ")"; } class Route { public: vector<City> cities; vector<int> splits; bool allPositiveCities = true; Route(vector<City> cities) : cities(cities) { for (int i = 0; i < cities.size() - 1; i++) { splits.push_back(i + 1); if (cities[i].value < 0) { allPositiveCities = false; } } if (cities.size() > 0 && cities[cities.size() - 1].value < 0) { allPositiveCities = false; } sort(splits.begin(), splits.end(), [cities](const int& i1, const int& i2) { return (cities[i1 - 1].pos - cities[i1].pos) < (cities[i2 - 1].pos - cities[i2].pos); }); } friend std::ostream& operator<<(std::ostream& os, const Route& obj); long long int getSum() { if (cities.size() > 0) { return cities[0].value + cities[0].right; } return 0; } int getLength() { if (cities.size() == 0) { return 0; } return cities[cities.size() - 1].pos - cities[0].pos; } void fillSumToRight(long long int sum) { if (cities.size() > 0) { cities[0].right = sum - cities[0].value; cities[0].left = 0; } for (int i = 1; i < cities.size(); i++) { cities[i].left = cities[i - 1].left + cities[i - 1].value; cities[i].right = cities[i - 1].right - cities[i].value; } } void fillSumToLeft(long long int sum) { if (cities.size() > 0) { cities[cities.size() - 1].right = 0; cities[cities.size() - 1].left = sum - cities[cities.size() - 1].value; } for (int i = cities.size() - 2; i >= 0; i--) { cities[i].left = cities[i + 1].left - cities[i].value; cities[i].right = cities[i + 1].right + cities[i + 1].value; } } pair<Route, Route> splitBySegment(int elementsInFirst) { long long int sum = getSum(); Route first(vector<City>(cities.begin(), cities.begin() + elementsInFirst)); Route second(vector<City>(cities.begin() + elementsInFirst, cities.end())); long long int sumToRight = second.getSum(); second.fillSumToRight(sumToRight); first.fillSumToLeft(sum - sumToRight); return pair<Route, Route>(first, second); } bool canSplitOn(int elementInFirst) { return cities[elementInFirst - 1].left + cities[elementInFirst - 1].value >= 0 && cities[elementInFirst].right + cities[elementInFirst].value >= 0 ; } bool shouldNotBeAdded() { return allPositiveCities || cities.size() == 0; } }; std::ostream& operator<<(std::ostream& os, const Route& obj) { os << "Route(" << obj.allPositiveCities << endl; for (auto& city : obj.cities) { cout << "\t" << city << endl; } for (auto& split : obj.splits) { cout << "\tSplit" << split << endl; } return os << ")" << endl; } int main(int argc, char** argv) { int n; cin >> n; vector<City> route1; long long int wholeRouteSum = 0; for (int i = 0; i < n; i++) { int value; cin >> value; if (value == 0) { continue; } wholeRouteSum += value; City newCity; newCity.value = value; newCity.pos = i; route1.push_back(newCity); } Route route(route1); if (wholeRouteSum < 0) { cout << "-1" << endl; return 0; } route.fillSumToRight(wholeRouteSum); vector<Route> routes; routes.push_back(route); for (int i = 0; i < routes.size(); i++) { for (auto& split : routes[i].splits) { if (routes[i].canSplitOn(split)) { pair<Route, Route> newRoutes = routes[i].splitBySegment(split); routes.erase(routes.begin() + i); int k = i; if (!newRoutes.first.shouldNotBeAdded()) { routes.insert(routes.begin() + k++, newRoutes.first); } if (!newRoutes.second.shouldNotBeAdded()) { routes.insert(routes.begin() + k++, newRoutes.second); } i--; break; } } } int sum = 0; for (auto& route : routes) { sum += route.getLength(); } cout << sum << 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 | #include <iostream> #include <set> #include <vector> #include <algorithm> using namespace std; class City { public: int pos = 0; int value = 0; long long int left = 0; long long int right = 0; friend std::ostream& operator<<(std::ostream& os, const City& obj); }; std::ostream& operator<<(std::ostream& os, const City& obj) { return os << "City(" << obj.pos << "," << obj.value << "," << obj.left << "," << obj.right << ")"; } class Route { public: vector<City> cities; vector<int> splits; bool allPositiveCities = true; Route(vector<City> cities) : cities(cities) { for (int i = 0; i < cities.size() - 1; i++) { splits.push_back(i + 1); if (cities[i].value < 0) { allPositiveCities = false; } } if (cities.size() > 0 && cities[cities.size() - 1].value < 0) { allPositiveCities = false; } sort(splits.begin(), splits.end(), [cities](const int& i1, const int& i2) { return (cities[i1 - 1].pos - cities[i1].pos) < (cities[i2 - 1].pos - cities[i2].pos); }); } friend std::ostream& operator<<(std::ostream& os, const Route& obj); long long int getSum() { if (cities.size() > 0) { return cities[0].value + cities[0].right; } return 0; } int getLength() { if (cities.size() == 0) { return 0; } return cities[cities.size() - 1].pos - cities[0].pos; } void fillSumToRight(long long int sum) { if (cities.size() > 0) { cities[0].right = sum - cities[0].value; cities[0].left = 0; } for (int i = 1; i < cities.size(); i++) { cities[i].left = cities[i - 1].left + cities[i - 1].value; cities[i].right = cities[i - 1].right - cities[i].value; } } void fillSumToLeft(long long int sum) { if (cities.size() > 0) { cities[cities.size() - 1].right = 0; cities[cities.size() - 1].left = sum - cities[cities.size() - 1].value; } for (int i = cities.size() - 2; i >= 0; i--) { cities[i].left = cities[i + 1].left - cities[i].value; cities[i].right = cities[i + 1].right + cities[i + 1].value; } } pair<Route, Route> splitBySegment(int elementsInFirst) { long long int sum = getSum(); Route first(vector<City>(cities.begin(), cities.begin() + elementsInFirst)); Route second(vector<City>(cities.begin() + elementsInFirst, cities.end())); long long int sumToRight = second.getSum(); second.fillSumToRight(sumToRight); first.fillSumToLeft(sum - sumToRight); return pair<Route, Route>(first, second); } bool canSplitOn(int elementInFirst) { return cities[elementInFirst - 1].left + cities[elementInFirst - 1].value >= 0 && cities[elementInFirst].right + cities[elementInFirst].value >= 0 ; } bool shouldNotBeAdded() { return allPositiveCities || cities.size() == 0; } }; std::ostream& operator<<(std::ostream& os, const Route& obj) { os << "Route(" << obj.allPositiveCities << endl; for (auto& city : obj.cities) { cout << "\t" << city << endl; } for (auto& split : obj.splits) { cout << "\tSplit" << split << endl; } return os << ")" << endl; } int main(int argc, char** argv) { int n; cin >> n; vector<City> route1; long long int wholeRouteSum = 0; for (int i = 0; i < n; i++) { int value; cin >> value; if (value == 0) { continue; } wholeRouteSum += value; City newCity; newCity.value = value; newCity.pos = i; route1.push_back(newCity); } Route route(route1); if (wholeRouteSum < 0) { cout << "-1" << endl; return 0; } route.fillSumToRight(wholeRouteSum); vector<Route> routes; routes.push_back(route); for (int i = 0; i < routes.size(); i++) { for (auto& split : routes[i].splits) { if (routes[i].canSplitOn(split)) { pair<Route, Route> newRoutes = routes[i].splitBySegment(split); routes.erase(routes.begin() + i); int k = i; if (!newRoutes.first.shouldNotBeAdded()) { routes.insert(routes.begin() + k++, newRoutes.first); } if (!newRoutes.second.shouldNotBeAdded()) { routes.insert(routes.begin() + k++, newRoutes.second); } i--; break; } } } int sum = 0; for (auto& route : routes) { sum += route.getLength(); } cout << sum << endl; return 0; } |