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
#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct node {
	long long power_level;
	int cable_cost;
	
	node(long long p, int c) : power_level(p), cable_cost(c) {}
};

int nodes_sol[10000000];
vector<node> nodes;
map<long long, int, std::greater<long long>> besties;

int main(){
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    long long pwr = 0;
    int cable_cost = 0;
    int total_cable_cost = 0;
    for(int i = 0; i < n; ++i){
        long long a;
        cin >> a;
        if (a != 0){
			node n(pwr, cable_cost);
			if (pwr >= 0) {
				nodes.push_back(n);
			}
			pwr += a;
			total_cable_cost += cable_cost;
			cable_cost = 0;
		}
		cable_cost++;
    }

/*
    for(unsigned int i = 0; i < nodes.size(); ++i){
		cout << nodes[i].power_level << " ";
	}
	cout << endl;
	for(unsigned int i = 0; i < nodes.size(); ++i){
		cout << nodes[i].cable_cost << " ";
	}
	cout << endl;
	cout << "POWER: " << pwr << endl;
*/

	besties[pwr] = 0;
	long long max_pwr = pwr;
	
	if (pwr < 0) {
		cout << -1 << endl;
		return 0;
	}
	
/*
	// a bit more bruteish
	for (int i = nodes.size() - 1; i >= 0; --i) {
		long long power_level = nodes[i].power_level;
		if (power_level <= max_pwr){
			int cable_cost = nodes[i].cable_cost;
			int best_new = 0;
			for (unsigned int j = i+1; j < nodes.size(); ++j) {
				long long j_pw = nodes[j].power_level;
				int j_cable = nodes_sol[j];
				if (j_pw >= power_level) {
					if (j_cable + cable_cost > best_new) {
						best_new = j_cable+cable_cost;
					}
				}
			}
			if (cable_cost > best_new) best_new = cable_cost;
			nodes_sol[i] = best_new;
		}
	}
	
	cout << total_cable_cost - nodes_sol[0] << endl;
*/

	for(int i = nodes.size() - 1; i >= 0; --i) {
		long long power_level = nodes[i].power_level;
		int cable_cost = nodes[i].cable_cost;
		//cout << "Checking for " << power_level << " ...\n";
		if (power_level <= max_pwr){
			auto best_prev = --besties.upper_bound(power_level); // map is reversed -> upper_bound will find x < power_level -> --ub will give x >= power_level
			//cout << "Found " << best_prev->second << " at " << best_prev->first << endl;
			//cout << "Setting " << cable_cost + best_prev->second << " at " << power_level << "." << endl;
			//cout << "Erasing all lower keys." << endl;
			int new_cost = cable_cost + best_prev->second;
			besties[power_level] = new_cost;
			
			// do not include the new node in erasures
			while (best_prev != besties.end() && best_prev->first >= power_level) {
				best_prev++;
			}
			// remove all worse options
			while (best_prev != besties.end()){
				if (best_prev->second < new_cost){
					// cout << "Erasing " << best_prev->first << " (" << best_prev->second << ")\n";
					besties.erase(best_prev++);
				} else {
					break;
				}
			}
		}
	}
	
	cout << total_cable_cost - besties[0] << endl;

	
    return 0;
}