P5745 [Deep Basics Appendix B Example] Maximum Interval Sum

Given a sequence of $n$ positive integers $a_1, a_2, \cdots, a_n$ and an integer $m$, find a subinterval $[i, j]$, that is, a consecutive part of the sequence $a_i, a_{i + 1}, \cdots, a_{j - 1}, a_j$, such that the sum of this subinterval is as large as possible while not exceeding $m$. If multiple intervals meet the requirement, output the one with the smallest $i$.

The input has two lines. The first line contains two integers $n, m$. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$.

Output one line with three integers, representing the left endpoint, the right endpoint, and the cumulative sum of the interval that meets the requirement.

**Subtask 1** (10 points): $n \le 200$. **Subtask 2** (20 points): $n \le 3000$. **Subtask 3** (30 points): $n \le 10^5$. **Subtask 4** (40 points): $n \le 4 \times 10^6$. For $100\%$ of the testdata, $1 \leq n \leq 4 \times 10^6$, $1 \leq m \leq 10^9$, $0 \leq a_1, a_2, \cdots, a_n \leq 10^5$. Translated by ChatGPT 5