Codeforces Round 645 (Div. 2) |
---|
Закончено |
Вы давно влюблены в Коронавирус-тян, но до сих пор не знали, где она живёт. И буквально сейчас выяснили, что она живёт в далёком местечке под названием Ньаху.
Вы немедленно решили взять отпуск на своей скучной работы и навестить Коронавирус-тян. Ваш отпуск длится ровно $$$x$$$ дней, и ровно столько дней вы проведёте в гостях у подруги. В гостях вы проведёте ровно $$$x$$$ подряд идущих дней.
В Ньаху используется очень необычный календарь: всего в году $$$n$$$ месяцев, $$$i$$$-й месяц длится ровно $$$d_i$$$ дней. Дни в $$$i$$$-м месяце пронумерованы от $$$1$$$ до $$$d_i$$$. В Ньаху нет високосных годов.
Настроение Коронавирус-тян (и, соответственно, её желание вас обнять) зависит от номера дня в месяце. А именно, в $$$j$$$-й день месяца вы получаете $$$j$$$ объятий, если вы находитесь в гостях у Коронавирус-тян.
Вы знаете об этой особенности своей подруги и хотите спланировать свою поездку так, чтобы суммарно получить наибольшее возможное количество объятий (и тогда, быть может, вы сможете завоевать сердечко Коронавирус-тян).
Обратите внимание, ваша поездка не обязательно должна начаться и закончиться в одном и том же году.
В первой строке входных данных даны два натуральных числа $$$n$$$ и $$$x$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество месяцев в году и количество дней, которые вы можете провести в гостях у подруги.
Во второй строке даны $$$n$$$ целых чисел $$$d_1, d_2, \ldots, d_n$$$, где $$$d_i$$$ — количество дней в $$$i$$$-м месяце ($$$1 \le d_i \le 10^6$$$).
Гарантируется, что $$$1 \le x \le d_1 + d_2 + \ldots + d_n$$$.
Выведите единственное число — максимальное число объятий, которое вы можете получить от Коронавирус-тян за время лучшего отпуска в своей жизни.
3 2 1 3 1
5
3 6 3 3 3
12
5 6 4 2 3 1 3
15
В первом примере номера дней года (номера в соответствующих месяцах) имеет вид: $$$\{1,1,2,3,1\}$$$. Коронавирус-тян обнимет вас больше всего раз, если вы приедете в третий день года: $$$2+3=5$$$ объятий.
Во втором примере номера дней года (номера в соответствующих месяцах) имеет вид: $$$\{1,2,3,1,2,3,1,2,3\}$$$. Больше всего объятий вы получите если приедете в третий день года: $$$3+1+2+3+1+2=12$$$ объятий.
В третьем примере номера дней имеют вид: $$$\{1,2,3,4,1,2, 1,2,3, 1, 1,2,3\}$$$. Больше всего объятий вы получите если приедете в двенадцатый день года: подруга обнимет вас $$$2+3+1+2+3+4=15$$$ раз.
Название |
---|