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
#include<bits/stdc++.h>
#define INF 1000000000000000
using namespace std;
typedef long long ll;
ll t[500002][2];	//wartość, odległość
int n,si=0;
int main()
{
	scanf("%d",&n);
	ll buff;
	int od=0;
	for(int i=0;i<n;++i)
	{
		scanf("%lld",&buff);
		if(!buff)	++od;
		else
		{
			t[++si][0]=buff;
			t[si][1]=od;
			od=1;
		}
	}
	if(si==0)	si=1;
/*
	for(int i=1;i<=si;++i)	printf("(%lld, %lld) ",t[i][0],t[i][1]);
	printf("\n");
*/

	vector <vector<ll>> dp(si+1,vector<ll>(n+1,-INF));
	dp[1][0]=t[1][0];
	for(int i=2;i<=si;++i)
	{
		for(int j=0;j<=n;++j)
		{
			if(dp[i-1][j]>=0)	dp[i][j]=max(dp[i][j],t[i][0]);
			if(t[i][1]<=j)	dp[i][j]=max(dp[i][j],dp[i-1][j-t[i][1]]+t[i][0]);
		}
	}

/*
	for(int i=1;i<=si;++i)
	{
		for(int j=0;j<=n;++j)	printf("%lld\t",dp[i][j]);
		printf("\n");
	}
*/
	for(int j=0;j<=n;++j)
	{
		if(dp[si][j]>=0)
		{
			printf("%d\n",j);
			return 0;
		}
	}
	printf("-1\n");
}