978E Bus Video System
  anLrwkgbyYZS 2023年12月30日 7 0


 

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 xx is the number of passengers in a bus just before the current bus stop and yy is the number of passengers in the bus just after current bus stop, the system records the number y−xy−x. So the system records show how number of passengers changed.

The test run was made for single bus and nn bus stops. Thus, the system recorded the sequence of integers a1,a2,…,ana1,a2,…,an (exactly one number for each bus stop), where aiai is the record for the bus stop ii. The bus stops are numbered from 11 to nn 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 ww (that is, at any time in the bus there should be from 00 to ww passengers inclusive).

Input

The first line contains two integers nn and ww (1≤n≤1000,1≤w≤109)(1≤n≤1000,1≤w≤109) — the number of bus stops and the capacity of the bus.

The second line contains a sequence a1,a2,…,ana1,a2,…,an (−106≤ai≤106)(−106≤ai≤106), where aiai equals to the number, which has been recorded by the video system after the ii-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 ww. If the situation is contradictory (i.e. for any initial number of passengers there will be a contradiction), print 0.

Examples

input

Copy

3 5
2 1 -3

output

Copy

3

input

Copy

2 4
-1 1

output

Copy

4

input

Copy

4 10
2 4 1 2

output

Copy

2

Note

In the first example initially in the bus could be 00, 11 or 22 passengers.

In the second example initially in the bus could be 11, 22, 33 or 44 passengers.

In the third example initially in the bus could be 00 or 11 passenger.

 

思路:

先求出车上的最大上车人数 Max, 最大小车人数Min。

如果 Max > w(公交车最大容量) 或 Min > w 显然不可能,输出 0 。

设车中原本就有的人 数量为 num, num 需要满足 Min <= num <= w-Max :

(1)  如果 Min > w-Max , 上述式子不成立,输出 0 ;

(2)输出w-Max - Min + 1;

下面的参考代码不是严格按照这个思路。

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long LL;
LL a[1100];

int main()
{
    long long n, w;
    cin >> n >> w;
    for(int i=1; i<=n; i++) cin >> a[i];

    LL temp = 0;
    LL Max = 0, Min = 0;
    for(int i=1; i<=n; i++) {
         temp += a[i];
         if(temp > Max)
            Max = temp;

         if(temp < Min)
            Min = temp;
    }

    Min *= -1;

    if(Max > w || Min > w ) cout << "0" << endl;
    else {
        Max = w - Max;
        if(Min > Max) cout << "0" << endl;
        else cout << Max - Min + 1 << endl;
    }
    return 0;
}

 

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2023年12月30日 0

暂无评论

anLrwkgbyYZS