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
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second

pair<int, int> tab[500003];
long long S[500003];
long long wynik;
int N=1;

void szukaj(int poziom, long long akt, long long wart, long long suma)
{
    if(suma+akt>=wynik)return;
    if(wart< (-S[poziom+1]) )return;
    if(poziom==N)
    {
        if(wart>=0)wynik=min(wynik, akt+suma);
        return;
    }
    if(wart>=0)
        szukaj(poziom+1, 0, tab[poziom+1].s, suma+akt);
    szukaj(poziom+1, akt+tab[poziom+1].f-tab[poziom].f, wart+tab[poziom+1].s, suma);
    return;
}

int main()
{
    int n, a;
    long long spr=0;
    cin>>n;
    wynik=n-1;
    bool q=0;
    for(int i=1; i<=n; i++)
    {
        cin>>a;
        spr+=a;
        if(a<0)q=1;
        if(a!=0)
        {
            tab[N]= {i, a};
            N++;
        }
    }
    if(spr<0)
    {
        cout<<"-1";
        return 0;
    }
    if(q==0)
    {
        cout<<"0";
        return 0;
    }
    N--;
    for(int i=N; i>=1; i--)S[i]=tab[i].s+S[i+1];
    szukaj(1ll, 0ll, (long long)tab[1].s, 0ll);

    cout<<wynik;

    return 0;
}