Dog Walking
Contest: Educational Codeforces Round 128 (Rated for Div. 2)
Difficulty rating: 2400
Tags: brute force, greedy, math

You are walking with your dog, and now you are at the promenade. The promenade can be represented as an infinite line. Initially, you are in the point $$$0$$$ with your dog.

You decided to give some freedom to your dog, so you untied her and let her run for a while. Also, you watched what your dog is doing, so you have some writings about how she ran. During the $$$i$$$-th minute, the dog position changed from her previous position by the value $$$a_i$$$ (it means, that the dog ran for $$$a_i$$$ meters during the $$$i$$$-th minute). If $$$a_i$$$ is positive, the dog ran $$$a_i$$$ meters to the right, otherwise (if $$$a_i$$$ is negative) she ran $$$a_i$$$ meters to the left.

During some minutes, you were chatting with your friend, so you don't have writings about your dog movement during these minutes. These values $$$a_i$$$ equal zero.

You want your dog to return to you after the end of the walk, so the destination point of the dog after $$$n$$$ minutes should be $$$0$$$.

Now you are wondering: what is the maximum possible number of different integer points of the line your dog could visit on her way, if you replace every $$$0$$$ with some integer from $$$-k$$$ to $$$k$$$ (and your dog should return to $$$0$$$ after the walk)? The dog visits an integer point if she runs through that point or reaches in it at the end of any minute. Point $$$0$$$ is always visited by the dog, since she is initially there.

If the dog cannot return to the point $$$0$$$ after $$$n$$$ minutes regardless of the integers you place, print -1.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3000; 1 \le k \le 10^9$$$) — the number of minutes and the maximum possible speed of your dog during the minutes without records.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$), where $$$a_i$$$ is the number of meters your dog ran during the $$$i$$$-th minutes (to the left if $$$a_i$$$ is negative, to the right otherwise). If $$$a_i = 0$$$ then this value is unknown and can be replaced with any integer from the range $$$[-k; k]$$$.

Output format:
If the dog cannot return to the point $$$0$$$ after $$$n$$$ minutes regardless of the set of integers you place, print -1. Otherwise, print one integer — the maximum number of different integer points your dog could visit if you fill all the unknown values optimally and the dog will return to the point $$$0$$$ at the end of the walk.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
3 2
5 0 -4

Example output:
6

Example input:
6 4
1 -2 0 3 -4 5

Example output:
7

Editorial:
Consider every cyclic shift of the array $$$a$$$. Suppose that now the array $$$a$$$ starts from the position $$$i$$$ (the first element is $$$a[i]$$$ and the last element is $$$a[(i + n - 1) \% n]$$$). Assume that before the position $$$i$$$ our dog reached her minimum possible position and now the minimum position will not change. So our problem is to fill all zeros in the array $$$a$$$ in such a way that the maximum prefix sum of $$$a$$$ is the maximum possible and the total sum of $$$a$$$ is zero.
For simplicity, consider the array $$$b$$$ which is the $$$i$$$-th cyclic shift of $$$a$$$ (i. e. the first element $$$b[0]$$$ is $$$a[i]$$$, the second element $$$b[1]$$$ is $$$a[(i + 1) \% n]$$$, and so on). Let's iterate from left to right and maintain the current sum of the array $$$b$$$. Let this variable be $$$s$$$. Now, when we meet $$$b_j = 0$$$, we should replace it with the maximum possible value we can (because in such a way we will increase the maximum number of prefix sums). Let $$$x$$$ be the number of zeros in $$$b$$$ starting from the position $$$j + 1$$$. This value can be calculated in advance in $$$O(n)$$$ for every cyclic shift using suffix sums. Then the segment of positions we can have at the end is $$$[s - xk; s + xk]$$$ and we want to place the maximum possible value in $$$b[j]$$$ in such a way that this remaining segment (with addition of our current element) will cover $$$0$$$. This maximum value equals $$$b[j] = min(k, xk - s)$$$. If $$$b[j]$$$ becomes less than $$$-k$$$ then this cyclic shift is invalid, and we should skip it. Otherwise, let's add $$$b[j]$$$ to $$$s$$$ and proceed. If there are no values $$$b[j] < -k$$$, then we placed anything correctly.
Now can just simulate the movements of our dog to find the answer for the current cyclic shift. But there are cases when $$$a$$$ do not contain zeros, so these cases should be handled somehow (I just checked that after simulation we returned to $$$0$$$). If we returned to $$$0$$$, we can update the answer as the difference between the maximum and the minimum positions plus one. If there is no valid cyclic shift, then the answer is -1.
Time complexity: $$$O(n^2)$$$.