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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>

using namespace std;

struct TestCase
{
  int length;
  vector<int> production;
};

TestCase read_test_case();
void solve_test_case(const TestCase&);

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve_test_case(read_test_case());
}

TestCase read_test_case()
{
  TestCase test_case;
  cin >> test_case.length;
  test_case.production.resize(test_case.length);
  for (auto& p : test_case.production) cin >> p;
  return test_case;
}

bool satisfiable(const TestCase& test_case)
{
  return accumulate(
             test_case.production.begin(), test_case.production.end(), 0) >= 0;
}

bool is_ok(const TestCase& test_case, int mask)
{
  int i = 0;
  while (i < test_case.length)
  {
    int current_sum = test_case.production[i];
    while (i < test_case.length - 1 && (mask & (1 << i)))
    {
      current_sum += test_case.production[i + 1];
      i++;
    }

    if (current_sum < 0) return false;
    i++;
  }
  return true;
}

int popcount(int value)
{
  int cnt = 0;
  while (value > 0)
  {
    cnt += (value & 1);
    value >>= 1;
  }
  return cnt;
}

void solve_test_case(const TestCase& test_case)
{
  if (!satisfiable(test_case))
  {
    cout << -1 << "\n";
    return;
  }

  int min_cost = test_case.length;
  int min_mask = 0;
  for (int m = 0; m < (1 << (test_case.length - 1)); m++)
  {
    if (is_ok(test_case, m))
    {
      int cost = popcount(m);
      if (cost < min_cost)
      {
        min_cost = cost;
        min_mask = m;
      }
    }
  }
  /*
  for (int i = 0; i < test_case.length - 1; i++)
  {
    if (abs(test_case.production[i]) > 9) cout << " ";
    if (test_case.production[i] < 0) cout << " ";
    cout << static_cast<bool>(min_mask & (1 << i)) << " ";
  }
  cout << "\n";
  */
  cout << min_cost << "\n";
}