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
#include<cstdio>
#include<vector>
#include<utility>

//nadmiar to to jaka mamy nadwyzke energetyczna w calym systemie
int solve(std::vector<int>::iterator act, std::vector<int>::iterator end, long long int nadmiar, long long bilans){
    int result = 0;
    if (nadmiar < 0)
	return -1;
    if (nadmiar == 0){
        while(act != end){
	    act++;
	    result++;
	}
	return result - 1;
    }
    if (act == end)
        return 0;
    if (bilans == 0){
	while((*act) == 0)
	    act++;
	    if (act == end)
		 return 0;
    }
		    
    long long int energia = bilans + (*act++);
    if (act == end){
	if (energia < 0)
	    return -1;
	else
	    return 0;
    }
    if (bilans > 0){
	while (energia >= bilans || energia < 0 || nadmiar < energia ){
	    result++;
	    energia += (*act++);
	    if(act == end){
		if(energia < 0 )
		    return -1;
		else
		    return result;
            }
	}
    }
    else if (bilans < 0 || (bilans == 0 && (*act) < 0)){
	if (bilans == 0){
	    result = 1;
	    energia = (*act++);
	    if (act == end)
	        return -1; //do wywalenia, nie powinno nigdy sie wydarzyc
	}	
        while (energia < 0 || nadmiar < energia){
            result++;
    	    energia += (*act++);
	    if(act == end){
                if(energia < 0 )
                    return -1;
                else
                    return result;
            }
	}
    }
    int r1, r2;
    if (energia == 0)
	return result + solve(act, end, nadmiar - energia, 0);
    
    r1 = result + 1 + solve(act, end, nadmiar, energia);
    if (nadmiar >= energia){
        r2 = result + solve(act, end, nadmiar - energia, 0);
    }
    else
	r2 = r1;

    return std::min(r1,r2);
}



int main(){
    int n;
    scanf("%d", &n);
    std::vector<int> miasta(n);
    long long int suma = 0;
    int bilans;
    for(int i=0; i<n; i++){
        scanf("%d", &bilans);
        suma += bilans;
        miasta[i] = bilans;
    }
    int result = solve(miasta.begin(), miasta.end(), suma, 0);
    printf("%d\n", result);
    return 0;   
}