cf978E Bus Video System
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 y−x. So the system records show how number of passengers changed.
The test run was made for single bus and 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 passengers inclusive).
Input
The first line contains two integers (1≤n≤1000,1≤w≤109) — the number of bus stops and the capacity of the bus.
The second line contains a sequence 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 0.
Examples
3 5
2 1 -3
3
2 4
-1 1
4
4 10
2 4 1 2
2
Note
In the first example initially in the bus could be 2 passengers.
In the second example initially in the bus could be 4 passengers.
In the third example initially in the bus could be 1 passenger.
题解：
只需要从后向前找出人最多的时刻，和最少的时刻。
#include <bits/stdc++.h>
using namespace std;
const int MAXN=200010;
const int INF=0x3f3f3f3f;
int sum[MAXN];
int main()
{
int n,w,a;
scanf("%d%d",&n,&w);
int MAX=0,MIN=INF;
for (int i = 1; i <=n ; ++i) {
scanf("%d",&a);
sum[i]=sum[i-1]+a;
MAX=max(MAX,sum[i]);
MIN=min(MIN,sum[i]);
}
MAX=w-MAX;
MIN=MIN>0?0:-MIN;
if(MAX-MIN+1<0) printf("0
");
else printf("%d
",MAX-MIN+1);
return 0;
}