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


int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n+1, 0);
    std::vector<long long int> partial(n+1, 0);
    for(int i = 1; i <= n; i++) {
        std::cin >> a[i];
        partial[i] = partial[i-1] + a[i];
    }

    std::vector<int> solution(n+1, -1);
    solution[0] = 0;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            if(partial[i]-partial[j-1] >= 0 && solution[j-1] != -1) {
                int candidate = i - j + solution[j-1];
                if(solution[i] == -1 || solution[i] > candidate) {
                       solution[i] = candidate;
                   }
            }
        }
        if(a[i] > 0 && solution[i-1] != -1) {
            if(solution[i] == -1 || solution[i] > solution[i-1])
                solution[i] = solution[i-1];
        }
    }

    std::cout << solution[n] << std::endl;

}