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

typedef long long int ll;

struct Point
{
	int pos;
	int len;
	ll value;
};
std::vector<Point> points;
int num_points;
int max_res;

int check(int bit_mask)
{
	int res=max_res;
	ll sum=0;
	for(int i=0;i<num_points;++i)
	{
		sum+=points[i].value;
		if((1<<i)&bit_mask)
		{
			if(sum<0) return 0;
			sum=0;
			res-=points[i].len;
		}
	}
	return res;
}

int brute_force()
{
	num_points=points.size();
	if(!num_points) return 0;
	if(num_points==1) return points[0].value>0?0:-1;

	max_res=points.back().pos-points[0].pos;
	for(int i=0;i<(int)points.size();++i)
		points[i].len=(i==points.size()-1)?0:(points[i+1].pos-points[i].pos);

	int range=1<<(num_points-1);
	int res=max_res;
	for(int i=0;i<range;++i)
	{
		int local_res=check(i|range);
		if(local_res&&local_res<res)
			res=local_res;
	}
	return res;
}

int main()
{
	int n;
	std::cin >> n;
	ll sum=0;
	for(int i=0;i<n;++i)
	{
		ll a;
		std::cin >> a;
		if(a)
		{
			points.push_back({i,0,a});
			sum+=a;
		}
	}
	if(sum<0)
		std::cout << -1;
	else if(sum==0)
		std::cout << (points.empty()?0:(points.back().pos-points[0].pos));
	else
		std::cout << brute_force();
}