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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

#define INFTY 1000000000LL*1000000000LL

/*

dynamik O(n^2).
t[i][j] = maksymalna nadwyżka energii dla miast 0..i, jeśli dla tych miast zbudujemy j połączeń.
t[i][j] < 0 oznacza, że jeśli z prawej dostarczymy -t[i][j] energii, to nakarmimy wszystkie miasta 0..i.
t[i][j] == -INFTY oznacza, że nie da się nakarmić miast 0..i, niezależnie od tego ile energii dostarczymy z prawej 

*/


int main()
{
    int n, prev_i;
    LL x;
    cin >> n;
    
    vector<LL> a;
    vector<int> dist {0}; //dist[i] == odległość i od i-1; dist[0] nieużywane
        
    prev_i = -1;
    for (int i=0; i<n; i++)
    {
      cin >> x;
      if (x != 0)
      {
        a.push_back(x);
        if (prev_i != -1)
          dist.push_back(i-prev_i);
        prev_i = i;  
      }  
    }
    
    int max_cost = n-1;
    n = a.size();
    
    if (n == 0)
    {
      cout << "0\n";
      return 0;
    }

    vector<vector<LL> > t(n,vector<LL>(max_cost+1));
    
    for (int j=0; j<=max_cost; j++)
      t[0][j] = a[0]; // nigdy nie ma -INFTY bo z prawej można dostarczyć energię.
      
    for (int i=1; i<n; i++)
    {
      if (t[i-1][0] < 0) 
        t[i][0] = -INFTY; //wcześniejszych miast się nie da przy zerowym koszcie lub potrzebują energii => 0..i też się da przy koszcie 0.
      else
        t[i][0] = a[i]; // wcześniejsze miasta są elektrowniami. nadwyżka w i wynosi a[i]. 
        
      for (int j=1; j<=max_cost; j++)
      {
        t[i][j] = -INFTY; 
        
        if (j >= dist[i])
          if (t[i-1][j-dist[i]] > -INFTY)
            t[i][j] = t[i-1][j-dist[i]] + a[i]; // odpowiada połączeniu i z (i-1).
    
        if (t[i-1][j] >= 0)
          t[i][j] = max(t[i][j], a[i]); // a[i] odpowiada brakowi połączenia i z (i-1). 
      }  
    }  
    
    int j;
    for (j=0; j<=max_cost; j++)
      if (t[n-1][j] >= 0) // tzn. miasta 0..n-1 mają nadwyżkę jeśli zapłacimy j połączeń.
        break;
      
    if (j<=max_cost)
      cout << j << "\n";
    else
      cout << -1;  

    return 0;
}