#include <vector> #include <cstdio> #include <map> #include <algorithm> #include <climits> int main() { int n; scanf("%d", &n); std::vector<long> a(n, 0); for (int i = 0; i < n; ++i) scanf("%ld", &a[i]); // moc -> koszt poczatkowy + poczatek std::map<long long, std::pair<unsigned long long,int>> costs; costs[0] = std::make_pair(0, 0); long long power_offset = 0; int last_i = 0; for (int i = 0; i < n; ++i) { if (a[i] != 0) { if (costs.rbegin()->first + power_offset >= 0) { auto c = costs.upper_bound(-power_offset-1); if ((c->first + power_offset) >= 0) { unsigned long long min_cost = c->second.first + (last_i - c->second.second); auto it = costs.find(-power_offset); if (it == costs.end() || ((it->second.first + (i - it->second.second)) >= min_cost)) { costs[-power_offset] = std::make_pair(min_cost, i); it = costs.find(-power_offset); if (std::next(it) != costs.end()) it++; min_cost = it->second.first + (i - it->second.second); while (it != costs.begin()) { --it; if (min_cost < it->second.first + (i - it->second.second)) { //printf("erase %lld %lld\n", it->first + power_offset, min_cost); it = costs.erase(it); } min_cost = std::min(min_cost, it->second.first + (i - it->second.second)); } } } } power_offset += a[i]; last_i = i; /* printf("i: %d, = %ld, ps = %lld\n", i, a[i], power_offset); for (const auto &c : costs) { printf("\t%lld -> %lld (cost: %lld, i: %d)\n", c.first + power_offset, c.second.first + (last_i - c.second.second), c.second.first, c.second.second); }//*/ } } auto c = costs.upper_bound(-power_offset-1); if (c->first + power_offset >= 0) { printf("%lld\n", c->second.first + (last_i - c->second.second)); } else { puts("-1"); } 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 | #include <vector> #include <cstdio> #include <map> #include <algorithm> #include <climits> int main() { int n; scanf("%d", &n); std::vector<long> a(n, 0); for (int i = 0; i < n; ++i) scanf("%ld", &a[i]); // moc -> koszt poczatkowy + poczatek std::map<long long, std::pair<unsigned long long,int>> costs; costs[0] = std::make_pair(0, 0); long long power_offset = 0; int last_i = 0; for (int i = 0; i < n; ++i) { if (a[i] != 0) { if (costs.rbegin()->first + power_offset >= 0) { auto c = costs.upper_bound(-power_offset-1); if ((c->first + power_offset) >= 0) { unsigned long long min_cost = c->second.first + (last_i - c->second.second); auto it = costs.find(-power_offset); if (it == costs.end() || ((it->second.first + (i - it->second.second)) >= min_cost)) { costs[-power_offset] = std::make_pair(min_cost, i); it = costs.find(-power_offset); if (std::next(it) != costs.end()) it++; min_cost = it->second.first + (i - it->second.second); while (it != costs.begin()) { --it; if (min_cost < it->second.first + (i - it->second.second)) { //printf("erase %lld %lld\n", it->first + power_offset, min_cost); it = costs.erase(it); } min_cost = std::min(min_cost, it->second.first + (i - it->second.second)); } } } } power_offset += a[i]; last_i = i; /* printf("i: %d, = %ld, ps = %lld\n", i, a[i], power_offset); for (const auto &c : costs) { printf("\t%lld -> %lld (cost: %lld, i: %d)\n", c.first + power_offset, c.second.first + (last_i - c.second.second), c.second.first, c.second.second); }//*/ } } auto c = costs.upper_bound(-power_offset-1); if (c->first + power_offset >= 0) { printf("%lld\n", c->second.first + (last_i - c->second.second)); } else { puts("-1"); } return 0; } |