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
#include <bits/stdc++.h>
#define ll long long
#define sz(x) x.size()

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
    ll n;
    cin >> n;
    vector<ll> a(n);
    for(ll &i : a) cin >> i;
    vector<ll> psum(n+1, 0);
    for(int i = 1; i <= n; i++) {
        psum[i] = psum[i - 1] + a[i - 1];
    }
    if(psum[n] < 0) {
        cout << "-1\n";
        return 0;
    }
    vector<vector<ll> > dp(n+1, vector<ll>(n+1, 1000000000));
    dp[0][0] = 0;
    for(int i = 0; i < n - 1; i++) {
        for(int j = 0; j < i + 2; j++) {
            if(dp[i][j] == 1000000000) continue;
            dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + 1);
            if(psum[i + 1] - psum[i - j] >= 0 && psum[n] - psum[i + 1] >= 0) dp[i + 1][0] = min(dp[i + 1][0], dp[i][j]);
        }
    }
    ll ans = 1000000000;
    for(int i = 0; i < n; i++) ans = min(ans, dp[n - 1][i]);
    cout << ans << '\n';
}