[Solution] Dog Walking solution codeforces

Dog Walking solution codeforces – 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 00 with your dog.

[Solution] Dog Walking solution codeforces

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 𝑎𝑖ai (it means, that the dog ran for 𝑎𝑖ai meters during the 𝑖i-th minute). If 𝑎𝑖ai is positive, the dog ran 𝑎𝑖ai meters to the right, otherwise (if 𝑎𝑖ai is negative) she ran 𝑎𝑖ai 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 𝑎𝑖ai 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 00.

Now you are wondering: what is the maximum possible number of different integer points of the line your dog could have visited, if you replace every 00 with some integer from 𝑘−k to 𝑘k (and your dog should return to 00 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 00 is always visited by the dog, since she is initially there.

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

[Solution] Dog Walking solution codeforces

The first line of the input contains two integers 𝑛n and 𝑘k (1𝑛3000;1𝑘1091≤n≤3000;1≤k≤109) — 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 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (109𝑎𝑖109−109≤ai≤109), where 𝑎𝑖ai is the number of meters your dog ran during the 𝑖i-th minutes (to the left if 𝑎𝑖ai is negative, to the right otherwise). If 𝑎𝑖=0ai=0 then this value is unknown and can be replaced with any integer from the range [𝑘;𝑘][−k;k].

Output

If the dog cannot return to the point 00 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 00 at the end of the walk.

Examples
input

Copy
3 2
5 0 -4

[Solution] Dog Walking solution codeforces

output

Copy
6
input

Copy
6 4
1 -2 0 3 -4 5
output

Copy
7
input

Copy
3 1000000000
0 0 0
output

Copy
1000000001
input

Copy
5 9
-7 -3 8 12 0

[Solution] Dog Walking solution codeforces

output

Copy
-1
input

Copy
5 3
-1 0 3 3 0
output

Copy
7
input

Copy
5 4
0 2 0 3 0
output

Copy
9

 

For Solution

Click here

Leave a Comment