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
73
74
75
76
77
78
79
#include <iostream>

using namespace std;

long iStan[500000], iDroga[500000];
long long iMiasta, iBilans, iMinimum, iAkt;

long szukaj(long start, long long bilans) {
    long i, j;
    if (start == iMiasta - 1) {
        if (iAkt < iMinimum) { 
            iMinimum = iAkt; 
            //cout << "minimum=" << iMinimum << endl; 
        }
        return 0;
    }
    if (iStan[start] < 0 || bilans - iStan[start] < 0) {
        if (iAkt + iDroga[start] >= iMinimum) {
            return -1;
        }
        iStan[start + 1] += iStan[start];
        iAkt += iDroga[start];
        i = szukaj(start + 1, bilans);
        iStan[start + 1] -= iStan[start];
        iAkt -= iDroga[start];
        return i + iDroga[start];
    }
    iStan[start + 1] += iStan[start];
    iAkt += iDroga[start];
    i = szukaj(start + 1, bilans);
    if (i != -1) i+= iDroga[start];
    iStan[start + 1] -= iStan[start];
    iAkt -= iDroga[start];

    j = szukaj(start + 1, bilans - iDroga[start]);

    if (i == -1) return j;
    if (j == -1) return i;

    return i < j ? i : j;
}

int main()
{
    long n, i, x;

    cin >> n;
    i = 0;
    while (i < n) {
        cin >> x; i++;
        if (x != 0) break;
    }
    if (i == n) { cout << 0; return 0; }
    iMiasta = 1; iDroga[0] = 1; iMinimum = n;
    iStan[0] = iBilans = x;
    while (i < n) {
        cin >> x;
        if (x != 0) {
            iStan[iMiasta] = x; iDroga[iMiasta++] = 1;
            iBilans += x;
        }
        else iDroga[iMiasta - 1]++;
        i++;
    }
    if (iBilans < 0) { cout << -1; return 0; }

    iAkt = 0;
    while (iStan[iMiasta - 1] < 0) {
        iStan[iMiasta - 2] += iStan[iMiasta - 1];
        iAkt += iDroga[iMiasta - 2];
        iMiasta--;
    }

    //for (i = 0; i < iMiasta; i++) { cout << "iDroga[" << i << "]=" << iDroga[i] << " iStan=" << iStan[i] << endl; }

    cout << szukaj(0, iBilans) + iAkt;

    return 0;
}