P1569 [USACO ?] Generic Cow Protests [Source Request]

Farmer John’s $n$ cows gather and line up in a row to stage a protest. The $i$-th cow has a rationality value $a_i$. He wants the cows to remain rational; to that end, he plans to partition all the cows into several groups such that within each group the sum of rationality values is at least zero. Since the cows are arranged in a straight line, each group must be a contiguous segment. Please help John compute the maximum number of groups.

The first line contains a positive integer $n$, the number of cows. The next $n$ lines each contain one integer, the rationality value of each cow.

If a valid partition exists, output one line with a single integer, the answer; otherwise output `Impossible`.

Constraints - For 30% of the testdata, $1 \le n \le 20$. - For 100% of the testdata, $1 \le n \le 1000$, $|a_i| \le 10^5$. Translated by ChatGPT 5