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

int E[500000];
int S[500000];


int main() {
  int N; scanf("%d", &N);
  for (int i = 0; i < N; i++) scanf("%d", &E[i]);

  S[0] = (E[0] >= 0) ? 0 : 1000000001;
  for (int k = 1; k < N; k++) {
    S[k] = 1000000001;
    long long sum = 0;
    for (int j = k; j >= 1; j--) {
      sum += E[j];
      if (sum >= 0) S[k] = min(S[k], S[j-1] + (k-j));
    }
    sum += E[0];
    if (sum >= 0) S[k] = min(S[k], k);
  }

  if (S[N-1] != 1000000001)
    printf("%d\n", S[N-1]);
  else
    printf("-1\n");

  return 0;
}