English · Original
Chinese · Translation
Formal · Original
The busses in Berland are equipped with a video surveillance system. The system records information about changes in the number of passengers in a bus after stops.
If $x$ is the number of passengers in a bus just before the current bus stop and $y$ is the number of passengers in the bus just after current bus stop, the system records the number $y-x$. So the system records show how number of passengers changed.
The test run was made for single bus and $n$ bus stops. Thus, the system recorded the sequence of integers $a_1, a_2, \dots, a_n$ (exactly one number for each bus stop), where $a_i$ is the record for the bus stop $i$. The bus stops are numbered from $1$ to $n$ in chronological order.
Determine the number of possible ways how many people could be in the bus before the first bus stop, if the bus has a capacity equals to $w$ (that is, at any time in the bus there should be from $0$ to $w$ passengers inclusive).
## Input
The first line contains two integers $n$ and $w$ $(1 \le n \le 1\,000, 1 \le w \le 10^{9})$ — the number of bus stops and the capacity of the bus.
The second line contains a sequence $a_1, a_2, \dots, a_n$ $(-10^{6} \le a_i \le 10^{6})$, where $a_i$ equals to the number, which has been recorded by the video system after the $i$\-th bus stop.
## Output
Print the number of possible ways how many people could be in the bus before the first bus stop, if the bus has a capacity equals to $w$. If the situation is contradictory (i.e. for any initial number of passengers there will be a contradiction), print _0_.
[samples]
## Note
In the first example initially in the bus could be $0$, $1$ or $2$ passengers.
In the second example initially in the bus could be $1$, $2$, $3$ or $4$ passengers.
In the third example initially in the bus could be $0$ or $1$ passenger.
伯兰的公交车配备了视频监控系统。该系统记录公交车在每站上下车后乘客数量的变化。
如果在当前公交站之前车上有 $x$ 名乘客，在当前公交站之后车上有 $y$ 名乘客，则系统记录数值 $y - x$。因此，系统记录显示了乘客数量的变化情况。
对一辆公交车进行了 $n$ 个公交站的测试运行。因此，系统记录了一个整数序列 $a_1, a_2, dots.h, a_n$（每个公交站恰好一个数值），其中 $a_i$ 是第 $i$ 个公交站的记录。公交站按时间顺序编号为 $1$ 到 $n$。
确定在第一个公交站之前车上有多少名乘客的可能方式数，假设公交车的容量为 $w$（即在任何时刻，车上的乘客数必须在 $0$ 到 $w$ 之间，包含端点）。
第一行包含两个整数 $n$ 和 $w$ $(1 lt.eq n lt.eq 1 thin 000, 1 lt.eq w lt.eq 10^9)$ —— 公交站数量和公交车容量。
第二行包含一个序列 $a_1, a_2, dots.h, a_n$ $(-10^6 lt.eq a_i lt.eq 10^6)$，其中 $a_i$ 表示第 $i$ 个公交站后视频系统记录的数值。
请输出在第一个公交站之前车上有多少名乘客的可能方式数，假设公交车容量为 $w$。如果情况矛盾（即无论初始乘客数是多少都会产生矛盾），请输出 _0_。
在第一个例子中，初始时车上有 $0$、$1$ 或 $2$ 名乘客。
在第二个例子中，初始时车上有 $1$、$2$、$3$ 或 $4$ 名乘客。
在第三个例子中，初始时车上有 $0$ 或 $1$ 名乘客。
## Input
第一行包含两个整数 $n$ 和 $w$ $(1 lt.eq n lt.eq 1 thin 000, 1 lt.eq w lt.eq 10^9)$ —— 公交站数量和公交车容量。第二行包含一个序列 $a_1, a_2, dots.h, a_n$ $(-10^6 lt.eq a_i lt.eq 10^6)$，其中 $a_i$ 表示第 $i$ 个公交站后视频系统记录的数值。
## Output
请输出在第一个公交站之前车上有多少名乘客的可能方式数，假设公交车容量为 $w$。如果情况矛盾（即无论初始乘客数是多少都会产生矛盾），请输出 _0_。
[samples]
## Note
在第一个例子中，初始时车上有 $0$、$1$ 或 $2$ 名乘客。在第二个例子中，初始时车上有 $1$、$2$、$3$ 或 $4$ 名乘客。在第三个例子中，初始时车上有 $0$ 或 $1$ 名乘客。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of bus stops.
Let $ w \in \mathbb{Z}^+ $ be the bus capacity.
Let $ A = (a_1, a_2, \dots, a_n) $ be the sequence of passenger changes at each stop, where $ a_i \in \mathbb{Z} $ is the net change after stop $ i $.
Let $ x_0 \in \mathbb{Z} $ be the initial number of passengers before the first stop.
For $ i \in \{1, \dots, n\} $, define $ x_i = x_0 + \sum_{j=1}^i a_j $ as the number of passengers after stop $ i $.
**Constraints**
1. $ 0 \le x_0 \le w $
2. For all $ i \in \{0, 1, \dots, n\} $: $ 0 \le x_i \le w $
Define the prefix sums:
Let $ s_0 = 0 $, and for $ i \in \{1, \dots, n\} $, let $ s_i = \sum_{j=1}^i a_j $.
Then $ x_i = x_0 + s_i $.
Thus, the constraints become:
For all $ i \in \{0, 1, \dots, n\} $:
$$
0 \le x_0 + s_i \le w
$$
Rewriting:
$$
- s_i \le x_0 \le w - s_i \quad \text{for all } i \in \{0, 1, \dots, n\}
$$
Define:
$$
L = \max_{i \in \{0, \dots, n\}} (-s_i), \quad U = \min_{i \in \{0, \dots, n\}} (w - s_i)
$$
**Objective**
Compute the number of integer values $ x_0 \in \mathbb{Z} $ satisfying:
$$
\max(0, L) \le x_0 \le \min(w, U)
$$
If $ \max(0, L) > \min(w, U) $, output $ 0 $.
Otherwise, output $ \min(w, U) - \max(0, L) + 1 $.
API Response (JSON)
{
"problem": {
"name": "E. Bus Video System",
"description": {
"content": "The busses in Berland are equipped with a video surveillance system. The system records information about changes in the number of passengers in a bus after stops. If $x$ is the number of passengers ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF978E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "The busses in Berland are equipped with a video surveillance system. The system records information about changes in the number of passengers in a bus after stops.\n\nIf $x$ is the number of passengers ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "伯兰的公交车配备了视频监控系统。该系统记录公交车在每站上下车后乘客数量的变化。\n\n如果在当前公交站之前车上有 $x$ 名乘客，在当前公交站之后车上有 $y$ 名乘客，则系统记录数值 $y - x$。因此，系统记录显示了乘客数量的变化情况。\n\n对一辆公交车进行了 $n$ 个公交站的测试运行。因此，系统记录了一个整数序列 $a_1, a_2, dots.h, a_n$（每个公交站恰好一个数值），其中 ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of bus stops. \nLet $ w \\in \\mathbb{Z}^+ $ be the bus capacity. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the sequence of passenger changes at ...",
"is_translate": false,
"language": "Formal"
}
]
}