[Solution] Dog Walking Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Dog Walking Codeforces Solution | Codeforces Problem Solution 2022

D. Dog Walking

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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$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.

Solution Click Below:-  CLICK HERE

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$0$.

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 0$0$ with some integer from −𝑘$-k$ to 𝑘$k$ (and your dog should return to 0$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$0$ is always visited by the dog, since she is initially there.

Minimums and Maximums Codeforces Solution 

Robots Codeforces Solution 

Binary String Codeforces Solution

Dog Walking Codeforces Solution

Moving Chips Codeforces Solution

Lenient Vertex Cover Codeforces Solution 

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

Input

The first line of the input contains two integers 𝑛$n$ and 𝑘$k$ (1≤𝑛≤3000;1≤𝑘≤109$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 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (−109≤𝑎𝑖≤109$-{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 𝑎𝑖=0$a_i=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 0$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$0$ at the end of the walk.

Join Now for Solution:-