CF1680D Dog Walking

你正在和你的狗散步，现在你们在一条长廊上。长廊可以看作是一条无限长的直线。最初，你和你的狗都在 $0$ 点。 你决定给你的狗一些自由，于是你解开了牵绳，让它自由奔跑一会儿。同时，你观察了狗的行动，并记录下了它的奔跑情况。在第 $i$ 分钟，狗的位置相对于前一分钟发生了 $a_i$ 的变化（也就是说，狗在第 $i$ 分钟内跑了 $a_i$ 米）。如果 $a_i$ 是正数，狗向右跑了 $a_i$ 米；如果 $a_i$ 是负数，狗向左跑了 $|a_i|$ 米。 在某些分钟里，你在和朋友聊天，因此没有记录下狗的运动情况。这些分钟对应的 $a_i$ 等于 $0$。 你希望狗在散步结束后能回到你身边，所以在 $n$ 分钟后，狗的位置应该回到 $0$ 点。 现在你想知道：如果你将每个 $0$ 替换为 $-k$ 到 $k$ 之间的某个整数（并且狗最终必须回到 $0$ 点），狗在途中最多可能经过多少个不同的整数点？如果狗在 $n$ 分钟后无论如何都无法回到 $0$ 点，请输出 $-1$。 狗经过一个整数点，指的是它在某一时刻经过该点，或者在某一分钟结束时正好到达该点。由于狗最初在 $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$ 点的情况下，狗最多可能经过多少个不同的整数点。

由 ChatGPT 4.1 翻译