309449: CF1680D. Dog Walking
Memory Limit：256 MB
Time Limit：4 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Dog Walking
题意翻译
有一个长度为 $n$ 的数列 $\{a\}$，用 $[-k,k]$ 之间的整数替换数列中每个为 $0$ 的位置，满足数列的和为 $0$，求从 $0$ 开始依次按数列移动（初始位置 $0$，每次加上 $a_i$），所能访问的整数点数量的最大值。题目描述
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.输入输出格式
输入格式
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] $ .
输出格式
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.
输入输出样例
输入样例 #1
3 2
5 0 -4输出样例 #1
6输入样例 #2
6 4
1 -2 0 3 -4 5输出样例 #2
7输入样例 #3
3 1000000000
0 0 0输出样例 #3
1000000001输入样例 #4
5 9
-7 -3 8 12 0输出样例 #4
-1输入样例 #5
5 3
-1 0 3 3 0输出样例 #5
7输入样例 #6
5 4
0 2 0 3 0输出样例 #6
9Input
题意翻译
有一个长度为 $n$ 的数列 $\{a\}$，用 $[-k,k]$ 之间的整数替换数列中每个为 $0$ 的位置，满足数列的和为 $0$，求从 $0$ 开始依次按数列移动（初始位置 $0$，每次加上 $a_i$），所能访问的整数点数量的最大值。Output
**题意翻译**
有一个长度为 $ n $ 的数列 $\{a\}$，用 $[-k,k]$ 之间的整数替换数列中每个为 $0$ 的位置，满足数列的和为 $0$，求从 $0$ 开始依次按数列移动（初始位置 $0$，每次加上 $a_i$），所能访问的整数点数量的最大值。
**题目描述**
你正在和你的狗散步，现在你在海滨长廊上。海滨长廊可以表示为一条无限长的直线。最初，你和你狗在点 $ 0 $。
你决定给你的狗一些自由，所以你解开了她的绳子，让她跑了一会儿。你还观察了你的狗在做什么，所以你有一些关于她的跑步的记录。在第 $ i $ 分钟，狗的位置从她之前的位置改变了 $ a_i $（这意味着在第 $ i $ 分钟内，狗跑了 $ a_i $ 米）。如果 $ a_i $ 是正数，狗向右跑了 $ a_i $ 米；否则（如果 $ a_i $ 是负数）她向左跑了 $ a_i $ 米。
在某些分钟里，你正在和你的朋友聊天，所以你没有记录你的狗在这些时间的移动。这些 $ a_i $ 的值等于 $ 0 $。
你希望你的狗在散步结束后回到你身边，所以狗在 $ n $ 分钟后的目的地应该是 $ 0 $。
现在你在想：如果你用 $[-k,k]$ 之间的整数替换每个 $ 0 $，你的狗在返回时可能访问的整点数的最大可能数是多少（狗在散步结束时必须回到 $ 0 $）？如果狗在任何分钟结束时跑过或到达某个点，她就会访问这个整点。点 $ 0 $ 总是被狗访问，因为她最初在那里。
如果无论你放置什么整数，狗在 $ n $ 分钟后都不能回到点 $ 0 $，打印 -1。
**输入输出格式**
**输入格式**
输入的第一行包含两个整数 $ n $ 和 $ k $（$ 1 \le n \le 3000; 1 \le k \le 10^9 $）——分钟数和在没有记录的分钟内狗的最大可能速度。
第二行输入包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ -10^9 \le a_i \le 10^9 $），其中 $ a_i $ 是在第 $ i $ 分钟内狗跑的米数（如果 $ a_i $ 是负数，则向左，否则向右）。如果 $ a_i = 0 $，则这个值是未知的，可以用范围 $ [-k; k] $ 中的任何整数替换。
**输出格式**
如果无论你放置什么整数，狗在 $ n $ 分钟后都不能回到点 $ 0 $，打印 -1。否则，打印一个整数——如果你以最佳方式填充所有未知值，并且狗在散步结束时回到点 $ 0 $，狗可能访问的不同整点数的最大值。**题意翻译** 有一个长度为 $ n $ 的数列 $\{a\}$，用 $[-k,k]$ 之间的整数替换数列中每个为 $0$ 的位置，满足数列的和为 $0$，求从 $0$ 开始依次按数列移动（初始位置 $0$，每次加上 $a_i$），所能访问的整数点数量的最大值。 **题目描述** 你正在和你的狗散步，现在你在海滨长廊上。海滨长廊可以表示为一条无限长的直线。最初，你和你狗在点 $ 0 $。 你决定给你的狗一些自由，所以你解开了她的绳子，让她跑了一会儿。你还观察了你的狗在做什么，所以你有一些关于她的跑步的记录。在第 $ i $ 分钟，狗的位置从她之前的位置改变了 $ a_i $（这意味着在第 $ i $ 分钟内，狗跑了 $ a_i $ 米）。如果 $ a_i $ 是正数，狗向右跑了 $ a_i $ 米；否则（如果 $ a_i $ 是负数）她向左跑了 $ a_i $ 米。 在某些分钟里，你正在和你的朋友聊天，所以你没有记录你的狗在这些时间的移动。这些 $ a_i $ 的值等于 $ 0 $。 你希望你的狗在散步结束后回到你身边，所以狗在 $ n $ 分钟后的目的地应该是 $ 0 $。 现在你在想：如果你用 $[-k,k]$ 之间的整数替换每个 $ 0 $，你的狗在返回时可能访问的整点数的最大可能数是多少（狗在散步结束时必须回到 $ 0 $）？如果狗在任何分钟结束时跑过或到达某个点，她就会访问这个整点。点 $ 0 $ 总是被狗访问，因为她最初在那里。 如果无论你放置什么整数，狗在 $ n $ 分钟后都不能回到点 $ 0 $，打印 -1。 **输入输出格式** **输入格式** 输入的第一行包含两个整数 $ n $ 和 $ k $（$ 1 \le n \le 3000; 1 \le k \le 10^9 $）——分钟数和在没有记录的分钟内狗的最大可能速度。 第二行输入包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ -10^9 \le a_i \le 10^9 $），其中 $ a_i $ 是在第 $ i $ 分钟内狗跑的米数（如果 $ a_i $ 是负数，则向左，否则向右）。如果 $ a_i = 0 $，则这个值是未知的，可以用范围 $ [-k; k] $ 中的任何整数替换。 **输出格式** 如果无论你放置什么整数，狗在 $ n $ 分钟后都不能回到点 $ 0 $，打印 -1。否则，打印一个整数——如果你以最佳方式填充所有未知值，并且狗在散步结束时回到点 $ 0 $，狗可能访问的不同整点数的最大值。
有一个长度为 $ n $ 的数列 $\{a\}$，用 $[-k,k]$ 之间的整数替换数列中每个为 $0$ 的位置，满足数列的和为 $0$，求从 $0$ 开始依次按数列移动（初始位置 $0$，每次加上 $a_i$），所能访问的整数点数量的最大值。
**题目描述**
你正在和你的狗散步，现在你在海滨长廊上。海滨长廊可以表示为一条无限长的直线。最初，你和你狗在点 $ 0 $。
你决定给你的狗一些自由，所以你解开了她的绳子，让她跑了一会儿。你还观察了你的狗在做什么，所以你有一些关于她的跑步的记录。在第 $ i $ 分钟，狗的位置从她之前的位置改变了 $ a_i $（这意味着在第 $ i $ 分钟内，狗跑了 $ a_i $ 米）。如果 $ a_i $ 是正数，狗向右跑了 $ a_i $ 米；否则（如果 $ a_i $ 是负数）她向左跑了 $ a_i $ 米。
在某些分钟里，你正在和你的朋友聊天，所以你没有记录你的狗在这些时间的移动。这些 $ a_i $ 的值等于 $ 0 $。
你希望你的狗在散步结束后回到你身边，所以狗在 $ n $ 分钟后的目的地应该是 $ 0 $。
现在你在想：如果你用 $[-k,k]$ 之间的整数替换每个 $ 0 $，你的狗在返回时可能访问的整点数的最大可能数是多少（狗在散步结束时必须回到 $ 0 $）？如果狗在任何分钟结束时跑过或到达某个点，她就会访问这个整点。点 $ 0 $ 总是被狗访问，因为她最初在那里。
如果无论你放置什么整数，狗在 $ n $ 分钟后都不能回到点 $ 0 $，打印 -1。
**输入输出格式**
**输入格式**
输入的第一行包含两个整数 $ n $ 和 $ k $（$ 1 \le n \le 3000; 1 \le k \le 10^9 $）——分钟数和在没有记录的分钟内狗的最大可能速度。
第二行输入包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ -10^9 \le a_i \le 10^9 $），其中 $ a_i $ 是在第 $ i $ 分钟内狗跑的米数（如果 $ a_i $ 是负数，则向左，否则向右）。如果 $ a_i = 0 $，则这个值是未知的，可以用范围 $ [-k; k] $ 中的任何整数替换。
**输出格式**
如果无论你放置什么整数，狗在 $ n $ 分钟后都不能回到点 $ 0 $，打印 -1。否则，打印一个整数——如果你以最佳方式填充所有未知值，并且狗在散步结束时回到点 $ 0 $，狗可能访问的不同整点数的最大值。**题意翻译** 有一个长度为 $ n $ 的数列 $\{a\}$，用 $[-k,k]$ 之间的整数替换数列中每个为 $0$ 的位置，满足数列的和为 $0$，求从 $0$ 开始依次按数列移动（初始位置 $0$，每次加上 $a_i$），所能访问的整数点数量的最大值。 **题目描述** 你正在和你的狗散步，现在你在海滨长廊上。海滨长廊可以表示为一条无限长的直线。最初，你和你狗在点 $ 0 $。 你决定给你的狗一些自由，所以你解开了她的绳子，让她跑了一会儿。你还观察了你的狗在做什么，所以你有一些关于她的跑步的记录。在第 $ i $ 分钟，狗的位置从她之前的位置改变了 $ a_i $（这意味着在第 $ i $ 分钟内，狗跑了 $ a_i $ 米）。如果 $ a_i $ 是正数，狗向右跑了 $ a_i $ 米；否则（如果 $ a_i $ 是负数）她向左跑了 $ a_i $ 米。 在某些分钟里，你正在和你的朋友聊天，所以你没有记录你的狗在这些时间的移动。这些 $ a_i $ 的值等于 $ 0 $。 你希望你的狗在散步结束后回到你身边，所以狗在 $ n $ 分钟后的目的地应该是 $ 0 $。 现在你在想：如果你用 $[-k,k]$ 之间的整数替换每个 $ 0 $，你的狗在返回时可能访问的整点数的最大可能数是多少（狗在散步结束时必须回到 $ 0 $）？如果狗在任何分钟结束时跑过或到达某个点，她就会访问这个整点。点 $ 0 $ 总是被狗访问，因为她最初在那里。 如果无论你放置什么整数，狗在 $ n $ 分钟后都不能回到点 $ 0 $，打印 -1。 **输入输出格式** **输入格式** 输入的第一行包含两个整数 $ n $ 和 $ k $（$ 1 \le n \le 3000; 1 \le k \le 10^9 $）——分钟数和在没有记录的分钟内狗的最大可能速度。 第二行输入包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ -10^9 \le a_i \le 10^9 $），其中 $ a_i $ 是在第 $ i $ 分钟内狗跑的米数（如果 $ a_i $ 是负数，则向左，否则向右）。如果 $ a_i = 0 $，则这个值是未知的，可以用范围 $ [-k; k] $ 中的任何整数替换。 **输出格式** 如果无论你放置什么整数，狗在 $ n $ 分钟后都不能回到点 $ 0 $，打印 -1。否则，打印一个整数——如果你以最佳方式填充所有未知值，并且狗在散步结束时回到点 $ 0 $，狗可能访问的不同整点数的最大值。