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
69
70
71
72
#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 500007;
long long pre[MAX_N], suf[MAX_N], a[MAX_N];
int n, result = 0, used = 0, toRight[MAX_N];
vector<long long>v;

bool Check() {
    for(int i = 0; i < n; i++) {
        long long sum = a[i];
        while(i < n - 1 && toRight[i])
            sum += a[++i];
        if(sum < 0)
            return false;
    }
    return true;
}

void Solve(int index) {
    if(index == n - 1) {
        if(Check())
            result = min(result, used);
        return;
    }
    toRight[index] = true;
    used++;
    Solve(index + 1);
    toRight[index] = false;
    used--;
    Solve(index + 1);
}

void Prepare() {
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i], pre[i] = suf[i] = a[i];
    for(int i = 1; i < n; i++)
        pre[i] = pre[i - 1] + a[i];
    for(int i = n - 2; i >= 0; i--)
        suf[i] = suf[i + 1] + a[i];
    for(int i = 0; i < n; i++)
        if(pre[i] < 0 || suf[i + 1] < 0)
            toRight[i] = true;
}

int main() {
    ios_base::sync_with_stdio(0);
    
    Prepare();
    if(pre[n - 1] < 0) {
        cout << "NIE\n";
        return 0;
    }
    v.reserve(n);
    for(int i = 0; i < n; i++) {
        long long sum = a[i];
        while(i < n - 1 && toRight[i])
            sum += a[++i], result++;
        v.push_back(sum);
    }
    for(int i = 0; i < v.size(); i++)
        a[i] = v[i];
    n = v.size();
    int temp = result;
    result = MAX_N;
    Solve(0);
    cout << result + temp << "\n";
    return 0;
}