#include <iostream> #include <vector> #include <algorithm> using namespace std; const int M = 1<<20; int64_t tree[20][M]; int64_t INF = -1e18; void init_tree() { for(int i = 0; i < 20; ++i) { for(int j = 0; j < M; ++j) { tree[i][j] = INF; } } } int64_t get_min_geq_than(int64_t a) { int64_t c = 0; for(int i = 19; i >= 0; --i) { if(tree[i][2*c] >= a) { c = c*2; } else if(tree[i][c*2+1] >= a) { c = c*2+1; } else { return INF; } } return c-(1<<19); } void append(int64_t el, int64_t cost) { cost += (1<<19); tree[0][cost] = el; int64_t c = cost; for(int i = 1; i < 20; ++i) { c /= 2; tree[i][c] = max(tree[i-1][2*c], tree[i-1][2*c+1]); } } int main() { init_tree(); ios_base::sync_with_stdio(false); int n; int64_t a; cin >> n; int64_t currentEl = 0; append(0, 0); for(int i = 0; i < n; ++i) { cin >> a; int64_t mini = get_min_geq_than(-currentEl); if(mini != INF) { append(-currentEl, mini-1); } currentEl += a; } int64_t result = get_min_geq_than(-currentEl); if(result == INF) { cout << "-1\n"; } else { cout << result+n << '\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 | #include <iostream> #include <vector> #include <algorithm> using namespace std; const int M = 1<<20; int64_t tree[20][M]; int64_t INF = -1e18; void init_tree() { for(int i = 0; i < 20; ++i) { for(int j = 0; j < M; ++j) { tree[i][j] = INF; } } } int64_t get_min_geq_than(int64_t a) { int64_t c = 0; for(int i = 19; i >= 0; --i) { if(tree[i][2*c] >= a) { c = c*2; } else if(tree[i][c*2+1] >= a) { c = c*2+1; } else { return INF; } } return c-(1<<19); } void append(int64_t el, int64_t cost) { cost += (1<<19); tree[0][cost] = el; int64_t c = cost; for(int i = 1; i < 20; ++i) { c /= 2; tree[i][c] = max(tree[i-1][2*c], tree[i-1][2*c+1]); } } int main() { init_tree(); ios_base::sync_with_stdio(false); int n; int64_t a; cin >> n; int64_t currentEl = 0; append(0, 0); for(int i = 0; i < n; ++i) { cin >> a; int64_t mini = get_min_geq_than(-currentEl); if(mini != INF) { append(-currentEl, mini-1); } currentEl += a; } int64_t result = get_min_geq_than(-currentEl); if(result == INF) { cout << "-1\n"; } else { cout << result+n << '\n'; } } |