P1714 Cutting Cake

Today is Xiao Z's birthday, and his classmates brought him a cake. The cake is a rectangular prism, divided into $n$ identical small pieces with different colors, and each small piece has a corresponding lucky value. As the birthday person, Xiao Z naturally wants the sum of lucky values of the cake he eats to be as large as possible, but Xiao Z can eat at most $m(m\le n)$ small pieces of cake. Please help him choose $k(1 \le k\le m)$ consecutive pieces among these $n$ pieces so that their total lucky value is maximized. Formally, in the sequence $\{p_n\}$, find a subsegment $[l,r](r-l+1\le m)$ that maximizes $\sum\limits_{i=l}^rp_i$.

The first line contains two integers $n,m$. They represent that there are $n$ small pieces in total, and Xiao Z can eat at most $m$ small pieces. The second line contains $n$ integers. The $i$-th integer $p_i$ represents the lucky value of the $i$-th small piece of cake.

Output a single integer in one line, which is the maximum lucky value Xiao Z can obtain.

Constraints and Conventions. - For $20\%$ of the testdata, $1\le n\le100$. - For $100\%$ of the testdata, $1\le n\le5\times 10^5$, $|p_i|≤500$. It is guaranteed that the absolute value of the answer is within $[0,2^{31}-1]$. Translated by ChatGPT 5