#P1662. 2024.1.31-华为秋招笔试-第二题-大礼包

2024.1.31-华为秋招笔试-第二题-大礼包

某公司日对新用户推出大礼包,从任意一天注册开始,连续登录xx天,每天可以领取一定的金币,领取金币的数量与该公司新设计的虚假世界的日历相关,该日历一年有nn个月,第ii个月有did_i天,每一年都一样。在每个月第一天会得到1个金币,第天会得到2个金币币第三天会得到3个金币,后面次类推。 请计算新用户注册后连续登陆xx天,最多可以获取多少金币。 请注意,连续登陆可能会跨年。

解答要求 时间限制:C/C++ 500ms,其他语言:1000ms

内存限制:C/C++ 256MB, 其他语言:512MB

输入

第一行包含两个整数nnx(1n2105)x(1\leq n\leq 2*10^{5}),分别表示一年中的月数和连续登陆的天数。第二行包含 nn 个整数 d1,d2,...,dnd_1,d_2,...,d_ndid_i表示第ii个月的天数(1di1061 ≤ d_i ≤ 10^{6}) 用例保证,1xd1+d2+...+dn1 \leq x \leq d_1+ d_2 + ...+ d_n

输出

打印新用户连续号陆x天最多可以获取的金币数量

样例1

输入

3 2
1 3 1

输出

5

解释

一年中每天获取的金币数是{1,1,2,3,1}\{1,1,2,3,1\}(对应每个月中的天数)。如果在一年中的第3天开始注册陆,最多可以获取 2+3=52+3=5 个金币。

样例2

输入

3 6
3 3 3

输出

12

解释

一年中每天获取的金币数是{1,2,3,1,2,3,1,2,3}\{1,2,3,1,2,3,1,2,3\}(对应每个月中的天数)。如果在一年中的第12天开始注册登陆,最多可以获取3+1+2+3+1+2=123+1+2+3+1+2=12个金币.

样例3

输入

5 6
4 2 3 1 3

输出

15

解释

一年中每天获取的金币数是{1,2,3,4,1,2,1,2,3,1,1,2,3}\{1,2,3,4,1,2,1,2,3,1,1,2,3\}(对应每个月中的天数)。如果在一年中的第12天开始注册登陆,最多可以获取2+3+1+2+3+4=152+3+1+2+3+4=15个金币