5398: P5745 【深基附B例】区间最大和

题目描述

给定 n 个正整数组成的数列 a₁, a₂, …, a_n 和一个整数 m。求出这个数列中的一个子区间 [i, j]，也就是在这个数列中连续的数字 a_i, a_{i + 1}, …, a_{j - 1}, a_j，使得这个子区间的和在不超过 m 的情况下最大。如果有多个区间符合要求，请输出 i 最小的那一个。

输入格式

输入共两行。

第一行，两个整数 n, m；

第二行，n 个整数 a₁, a₂, …, a_n。

输出格式

一行，三个整数，表示符合题意的区间的左端点、右端点和累加和。

输入输出样例 #1

输入 #1

5 10
2 3 4 5 6

输出 #1

1 3 9

说明/提示

子任务 1（10分）：n ≤ 200；

子任务 2（20分）：n ≤ 3000；

子任务 3（30分）：n ≤ 10⁵；

子任务 4（40分）：n ≤ 4 × 10⁶。

对于 100% 的数据，1 ≤ n ≤ 4 × 10⁶，1 ≤ m ≤ 10⁹，0 ≤ a₁, a₂, …, a_n ≤ 10⁵。

5 10
2 3 4 5 6

1 3 9