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

using namespace std;

int road(int* city, int n) {
    int road = 0, sum = city[0];
    for(int i = 1; i < n; i++) {
        if (sum!=0)
            road++;
        sum += city[i];
    }
    return road;
}

bool iterate(int* city, int* tmp, int n, int &sum) {
    for(int i = n - 1; i >= 0;) {
        if (tmp[i] < 0) {
            i--;
        }else
        if (tmp[i] + 1 > city[i]) {
            tmp[i] = 0;
            sum -= city[i];
            i--;
        }
        else {
            tmp[i]++;
            sum++;
            return true;
        }
    }
    return false;
}

int main()
{
    int n,sum=0,aim=0,min, now;
    cin >> n;
    min = n;
    int* city = new int[n];
    int* tmp = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> city[i];
    }
    for (int i = 0; i < n; i++) {
        if (city[i] < 0) {
            tmp[i] = city[i];
            aim -= city[i];
        }
        else {
            tmp[i] = 0;
        }
    }
    while (iterate(city,tmp,n,sum)) {
        if (sum == aim) {
            now = road(tmp, n);
            if (now < min) {
                min = now;
            }
        }
    }
    cout << min << endl;
return 0;
}