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
#include <iostream>
#include <vector>

#include <fstream>

int64_t PowerBalance(const std::vector<int64_t>& power, const int begin_idx, const int end_idx)
{
	int64_t balance = 0;
	for (int i = begin_idx; i <= end_idx; i++)
	{
		balance += power[i];
	}

	return balance;
}

int64_t FindMinCost(
	const std::vector<int64_t>& power,
	int begin_idx, int end_idx)
{
	// delete edge wires
	for (int i = begin_idx; i < end_idx; i++)
	{
		if (power[i] == 0)
			begin_idx++;
		else break;
	}
	for (int i = end_idx; i > begin_idx; i--)
	{
		if (power[i] == 0)
			end_idx--;
		else break;
	}

	int64_t rbalance = PowerBalance(power, begin_idx, end_idx);
	int64_t lbalance = 0;

	std::pair<int, int> c_gap(begin_idx, begin_idx);
	std::pair<int, int> b_gap(begin_idx, begin_idx);
	int64_t power_in_c_gap = 0;
	int64_t power_in_b_gap = 0;

	for (int i = begin_idx; i < end_idx; i++)
	{
		lbalance += power[i];
		rbalance -= power[i];
		bool balanced = (lbalance >= 0 && rbalance >= 0);
		bool is_factory = power[i] < 0;
		if (balanced && !is_factory)
		{
			c_gap.second++;
			if (power[i] > 0)
				power_in_c_gap += power[i];
		}
		else
		{
			if (c_gap.second - c_gap.first > b_gap.second - b_gap.first)
			{
				b_gap = c_gap;
				power_in_b_gap = power_in_c_gap;
			}

			if (balanced)
			{
				c_gap = { i, i + 1 };
			}
			else
			{
				c_gap = { i + 1, i + 1 };
			}

			power_in_c_gap = 0;
		}
	}


	if (b_gap.second - b_gap.first <= 0) return end_idx - begin_idx;
	else
	{
		return FindMinCost(power, begin_idx, b_gap.first) +
			FindMinCost(power, b_gap.second, end_idx);
	}
}

int main()
{
	// input
	int64_t n;
	std::cin >> n;
	std::vector<int64_t> power(n);
	for (int64_t i = 0; i < n; i++)
		std::cin >> power[i];

	// balance
	int64_t balance = PowerBalance(power, 0, power.size() - 1);
	if (balance < 0)
	{
		std::cout << -1;
		return 0;
	}

	std::cout << FindMinCost(power, 0, power.size() - 1u);

	return 0;
}