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>
#include <vector>
#include <tuple>


using namespace std;

pair<bool, int> petla_rekurencyjna(vector<int>::iterator begin, vector<int>::iterator end)
{
    if (end-begin==0) // empty sequence
        return make_pair(false, 0);

    if (end-begin==1) //1-element sequence
    {
        if (*begin <0)
            return make_pair(false, 0);
        else
            return make_pair(true, 0);
    }

    int koszt_opt = end-begin-1;
    vector<int64_t> suma_skumulowana;
    suma_skumulowana.assign(begin, end);
    for (auto it = suma_skumulowana.begin()+1; it!=suma_skumulowana.end(); ++it)
    {
            *it += *(it-1);
    }
    int64_t suma = suma_skumulowana.back();
    if (suma<0)
        return make_pair(false, koszt_opt);

    for (auto it = begin+1; it!=end; ++it)
    {
        bool czy_dziala1, czy_dziala2;
        int koszt1, koszt2;
        int indeks = it-begin;
        if (suma_skumulowana[indeks-1]>=0 && (suma - suma_skumulowana[indeks-1])>=0)
        {
            tie(czy_dziala1, koszt1) = petla_rekurencyjna(begin, it);
            tie(czy_dziala2, koszt2) = petla_rekurencyjna(it, end);

            if(czy_dziala1 && czy_dziala2) // podzial jest mozliwy
                koszt_opt = min(koszt_opt, koszt1 + koszt2);
        }
    }
    return make_pair(true, koszt_opt);
}


int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin>>n;

    vector<int> energia;

    for(int ii=0; ii<n; ii++)
    {
        int x;
        cin>>x;
        energia.push_back(x);
    }

    int koszt;
    bool czy_dziala;

    tie(czy_dziala, koszt) = petla_rekurencyjna(energia.begin(), energia.end());

    if (czy_dziala)
        cout<<koszt<<endl;
    else
        cout<<-1<<endl;


    return 0;
}