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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifdef LOCAL
#define debug(...) __VA_ARGS__
#else
#define debug(...) {}
#endif
ll dp[5001][5001];
const int base = (1<<19);
int base2 = base-1;
ll tree[2*base];
void change(int a, int b, ll x){
    a += base-1;
    b += base+1;
    while (b-a > 1){
        if (!(a%2)) tree[a+1] += x;
        if (b%2) tree[b-1] += x;
        a /= 2;
        b /= 2;
    }
}
ll query(int v){
    v += base;
    ll wy = 0;
    while (v){
        wy += tree[v];
        v /= 2;
    } 
    return wy;
}
int query2(int v){
    int p = v;
    int k = base2;
    int s;
    while (p < k){
        s = (p+k)/2;
        if (query(s) < 0) p = s+1;
        else k = s;
    }
    s = (p+k)/2;
    if (query(s) >= 0) return s;
    else return -1;
}
const ll INF = -2137213721372137;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie();
    cout.tie();
    debug(freopen("ele0.in","r",stdin););
    int i;
    int n;
    cin>>n;
    if (n > 5000){
        int fakewy = 0;
        int pointer = 0;
        ll akt;
        cin>>akt;
        tree[base2+base] = akt;
        for (i = 1; i < n; i++){
            cin>>akt;
            int s = query2(base2-pointer);
            bool fr = 0;
            if (query(base2-pointer) >= 0){
                pointer++;
                fr = 1;
            }
            else fakewy++;
            change(base2-pointer,base,akt);
            if (s != -1 && !fr){
                //cout<<s<<"\n";
                //cout<<s-moved<<" "<<query(s-moved)<<" "<<akt<<"\n";
                if (query(s-1) < akt){
                    tree[s+base-1] += akt-query(s-1);
                }
            }
            //cout<<fakewy<<" # ";
            //for (int j = base2-pointer; j < base2+1; j++) cout<<query(j)<<" ";
            //cout<<"\n";
            //return 0;
        }
        for (i = base2-pointer; i < base2+1; i++){
            if (query(i) >= 0){
                cout<<fakewy+(i-base2+pointer)<<"\n";
                return 0;
            }
        }
        cout<<-1<<"\n";
        return 0;
    }
    for (i = 0; i < n ; i++) dp[1][i] = INF;
    ll akt;
    cin>>akt;
    dp[1][0] = akt;
    for (i = 2; i < n+1; i++){
        cin>>akt;
        if (dp[i-1][0] >= 0) dp[i][0] = akt;
        else dp[i][0] = INF;
        for (int j = 1; j < n; j++){
            dp[i][j] = dp[i-1][j-1]+akt;
            if (dp[i-1][j] >= 0) dp[i][j] = max(dp[i][j],akt); 
            dp[i][j] = max(dp[i][j],INF);
            //cout<<i<<" "<<j<<" "<<dp[i][j]<<"\n"; 
        }
    }
    for (i = 0; i < n; i++){
        if (dp[n][i] >= 0){
            cout<<i<<"\n";
            return 0;
        }
    }
    cout<<-1<<"\n";
    return 0;
}