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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <map>
#include <iterator>

using namespace std;
multimap<int, int> tree;

#define MAX 555555

int min(int a, int b) {
    if (a < b) return a;
    return b;
}

typedef long long ll;
ll S[MAX];
int T[MAX], B[MAX];

int n;

int main()
{
    scanf("%d", &n);
    for (int i=1; i<=n; i++) {
        scanf("%lld", &T[i]);
        S[i] = T[i] + S[i-1];
        B[i] = MAX;
    }

    B[0] = 0;
    tree.insert(pair<int, int>(0, 0));
    for (int i=1; i<=n; i++) {
        B[i] = MAX;

        for (multimap<int, int>::iterator node=tree.begin(); node!=tree.end(); ++node) {
            int p = node->second;
            ll si = S[i] - S[p]; // suma interwalu (p, i]
            if (si >= 0) {
                B[i] = min(B[i], B[p]+(i-p-1));
                break;
            }
        }
        if (B[i] < MAX) {
            tree.insert(pair<int, int>(B[i]-i, i));
        }
    }

    if (B[n] == MAX) {
        printf("-1\n");
        return 0;
    }
    printf("%d\n", B[n]);
    return 0;
}