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
#include <cstdio>
using namespace std;

const int MAX_N = 500000;
long long t[MAX_N+3], sum[MAX_N+3];
int n;

int try_to_remove(const int &l, const int &r)
{
//    fprintf(stderr, "try_to_remove(%d, %d)\n", l, r);
    int new_removed, max_removed=0;
    for (int i=l; i<r; ++i) {
        if ((sum[i] - sum[l-1] >= 0) and (sum[r] - sum[i] >= 0)) {
//            fprintf(stderr, "L=%lld, R=%lld\n", sum[i]-sum[l-1], sum[r]-sum[i]);
            int ir = i+1;
            while (ir+1 <= r and t[ir] == 0)
                ++ir;
//            fprintf(stderr, "trying to remove [%d]..[%d]\n", i, ir);
            new_removed = ir - i + try_to_remove(ir, r);
            if (max_removed < new_removed)
                max_removed = new_removed;
            i = ir;
        }
    }
    return max_removed;
}

int main()
{
    scanf("%d", &n);
    sum[0] = 0;
    for (int i=1; i<=n; ++i) {
        scanf("%lld", &t[i]);
        sum[i] = sum[i-1] + t[i];
    }
    if (sum[n] < 0)
        printf("-1\n");
    else
        printf("%d\n", n-1-try_to_remove(1, n));
    return 0;
}