分析
看到这种题就可以想到动态规划，先设状态：$f_i$ 表示考虑前 $i$ 个数，所需要的最小代价。
发现 $f_i$ 可以从所有 $i$ 以前的状态加后一段区间转移过来，于是可以列出状态转移方程：
$$f_i = \min_{j = i - 1}^{s_i - s_j \leq m}(f_j + \max_{k = j + 1}^i)$$
其中 $j$ 是上一个区间的右端点，$s$ 数组为前缀和数组。
不难发现每次转移 $f_i$ 的复杂度是 $O(N)$ 的，总复杂度为 $O(N^2)$，无法通过此题。
考虑将 $f_i$ 的转移过程进行优化。
由题目的性质，可以发现 $f_i$ 有单调不降的性质，基于这一点，我们可以在转移时：
如果 $a_j \leq a_{j+1}$。
则 $\max_{k = j}^i = \max_{k = j + 1}^i$。
则 $f_{j-1} + \max_{k = j}^i \leq f_j + \max_{k = j + 1}^i$。
基于这一点，可以转移过来的状态就可以用单调队列来存储了，并且用 multiset 来确定最优状态。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 100010
int n, m, a[N], s[N], f[N], l, r, q[N << 2];
multiset<int> S;
signed main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (a[i] > m) //如果有大于m的数，肯定无解，直接输出-1。
{
cout << -1;
return 0;
}
s[i] = s[i - 1] + a[i];
}
l = 1;
r = 0;
for (int i = 1; i <= n; i++)
{
while (l <= r && s[i] - s[q[l]] > m) //如果当前区间和大于m，直接舍去。
{
S.erase(f[q[l]] + a[q[l + 1]]); //这里要加的是a[q[l+1]]，因为这是当前区间的最大值。
l++;
}
while (l <= r && a[q[r]] < a[i]) //如果前面的数比当前数小，就会算错当前区间最大值，所以这里要提前弹出这些数。
{
S.erase(f[q[r - 1]] + a[q[r]]);
r--;
}
if (l <= r) //如果弹完后，单调队列中还有元素，就可以加入以当前值作为最大值的答案。
{
S.insert(f[q[r]] + a[i]);
}
q[++r] = i;
int L = 0, R = i - 1, c;
while (L <= R) //这里求出距当前位置最远的区间左端点使区间的和小于等于m，为的是避免S中没有元素导致无法更新答案。
{
int mid = (L + R) >> 1;
if (s[i] - s[mid] > m)
{
L = mid + 1;
}
else
{
c = mid;
R = mid - 1;
}
}
f[i] = f[c] + a[q[l]]; //这种情况下的最大值为a[q[l]]。
if (S.size())
{
f[i] = min(f[i], *S.begin()); //如果S中有元素，就用S中最小的元素更新答案。
}
}
cout << f[n];
}