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
#include <iostream>
using namespace std;

int main() 
{
	int n;
	int t[500500];
	int w[500500], gdzie[500500], dokad, cof;

	int i,j;
	
	cin >> n;
	for (i=0; i<n; i++) cin >> t[i];

	w[0]=t[0];
	gdzie[0]=0;
	dokad=0;

		//i=0; cout << "Krok " << i << endl;
		//cout << "w: "; for (int qq=0; qq<=i; qq++) cout << w[qq] << " "; cout << endl;
		//cout << "gdzie: "; for (int qq=0; qq<=i; qq++) cout << gdzie[qq] << " "; cout << endl;
		//cout << "Dokad = " << dokad << endl;

	
	for (i=1; i<n; i++)
	{
		w[i]=w[i-1]+t[i];
		gdzie[i]=i;

		j=i;
		cof=1;
		while (j-->dokad) 
		{

			while (cof-j<=dokad && gdzie[j-cof]<=j-cof) cof++;
			//cout << "cof = " << cof << " j=" << j << " gdzie[j-cof] = " << gdzie[j-cof] << " || ";
			
			if (t[i]<0)
			{
				if (j-cof>=dokad)
				{
					if (w[j] >= 0)
					{
						if (t[i]+w[j-cof] > t[i]) w[j] = t[i]+w[j-cof]; else w[j]=t[i];
					}
					else w[j]=t[i]+w[j-cof];
				}
				else
				{
					if (w[j]<0) dokad = j+1;
					w[j] = t[i];
				}
				gdzie[j]=i;
			}
			if (t[i]>0)
			{
				if (j-cof>=dokad)
				{
					if (w[j] >= 0)
					{
						if (t[i]+w[j-cof] > t[i]) w[j] = t[i]+w[j-cof]; else w[j]=t[i];
					}
					else w[j] = t[i]+w[j-cof];
					gdzie[j]=i;
				}
				else
				{
					if (w[j]>=0) {w[j] = t[i]; gdzie[j]=i;}
					else dokad = j+1;
				}
			}
		}
		
		//cout << "Krok " << i << endl;
		//cout << "w: "; for (int qq=0; qq<=i; qq++) cout << w[qq] << " "; cout << endl;
		//cout << "gdzie: "; for (int qq=0; qq<=i; qq++) cout << gdzie[qq] << " "; cout << endl;
		//cout << "Dokad = " << dokad << endl;
	}
	
	for (i=0; i<n; i++) if (w[i]>=0) {cout << i; return 0;}
	cout << -1;
	return 0;
	
}