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
80
81
82
// Tadeusz Kielak

#include <iostream>

using namespace std;

#define MAX_MIAST 500001



long miasta[ MAX_MIAST ];


long n;



void show()
{
    long i;
    cout << "m:\t";
    for( i = 0; i < n; i ++ )
    {
        cout << miasta[ i ] << ' ';
    }
    cout << endl;

}


long koszt( long i, long j)
{
    long k, koszt_min, bilans_mocy, koszt_pom1, koszt_pom2;
    koszt_min = j - i - 1 ;
    bilans_mocy = 0;
    for( k = i; k < j - 1; k ++)
    {
        bilans_mocy += miasta[ k ];

  //       cout << i << " " << k  + 1 << '\t';
  //       cout << k + 1 << " " <<  j << '\n';

        koszt_pom1 = koszt( i, k + 1);

        koszt_pom2 = koszt( k +1, j );
        if( koszt_pom1 != -1 && koszt_pom2 != -1 )
            if( koszt_min > koszt_pom1 + koszt_pom2 )
                koszt_min = koszt_pom1 + koszt_pom2;
    }
    bilans_mocy += miasta[ j - 1];
    if( bilans_mocy < 0)
        return -1;

    return koszt_min;


}

int main()
{


    long i, j,bilans_mocy;

    bilans_mocy = 0;
    cin >> n;
    for( i = 0; i < n; i ++ )
    {
        cin >> j;
        miasta[ i ] = j;
        bilans_mocy += j;
    }
     if( bilans_mocy < 0 )
    {
        cout << -1 << '\n';
        return 0;
    }

    cout << koszt( 0, n ) << '\n';

    return 0;
}