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
#include <iostream>
#include <stdio.h>
#define INF 1000000000

using namespace std;

int n,r;
long long x;

int main()
{
    scanf("%d",&n);
    long long dp[n+1];
    for(int i=1;i<=n;i++) dp[i]=-INF;

    dp[0]=0;

    for(int i=1;i<=n;i++){
        scanf("%lld",&x);

        if(x<0) r=INF;
        
        for(int j=i;j;j--){
            if(dp[j]+x>=0) dp[j]=0;
            else dp[j]=-INF;

            if(dp[j]>=0) r=min(r,j);
            if(dp[j-1]+x>=0) r=min(r,j);
            
            dp[j]=max(dp[j],dp[j-1]+x);
        }
        if(dp[0]+x<0) dp[0]=-INF;
        
    }

    if(r>n||r<0) printf("-1\n");
    else printf("%d",r);

    return 0;
}