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

const long long infty = 1000000000000000;

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;

    long long maps[n];
    long long tab[n];
    long long partial[n+1];
    long long best[n];
    long long best_prev[n];

    for (int i=0; i<n; i++) {
        best[i] = infty;
        best_prev[i] = 0; 
    }

    for(int i=0; i<n; i++) {
        cin >> tab[i];
    }

    partial[0] = 0;
    for(int i=0; i<n; i++) {
        partial[i+1] = partial[i]+tab[i];
    }

    if (partial[n] < 0) {
        cout << "-1";
        return 0;
    }

    long long current = 0;
    for (int i=0; i<n; i++) {
        best_prev[i] = current;
        for (int j=i-1; j>=0; j--) {
            if(partial[i+1]-partial[j] >= 0) {
                best[i] = min(best[i], i-j+best_prev[j]);
            }
        }
        if (tab[i]<-1) {
            current = best[i];
        }
        else {
            current = min(current, best[i]);
            if (current==0) {
                current = best[i];
            }
        }        
    }

    long long result = infty;
    for (int i=n-1; i>=0; i--) {
        result = min(result, best[i]);
        if (tab[i] < 0) {
            break;
        }
    }


    cout <<result;
}