【原题见
这里】
本沙茶见过的最猥琐的DP题啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊……
设F[i]为将A[1..i]拆分成若干段的最大值最小和，则有
F[i]=min{F[j] + max[j+1, i]}（B[i]<=j<i），其中max[j+1, i]表示A[j+1..i]中的最大值，B[i]表示从i向左最远可以延伸到哪里（也就是满足SUM[x..i]<=m的最小的x值）。B数组可以通过预处理在O(N)时间内得到。
边界：F[0]=0。
下面是优化过程。JZP神犇的论文里面已经够详细了。这里只是简要说明一下。
首先容易证明，F是单调递增的。
然后一个很关键的定理是：
若F[i]的最优决策为j，则有A[j]>∀A[k]（j<k<=i）。证明：用反证法。若A[j+1..i]中存在不小于A[j]的值，则可得max[j..i]=max[j+1..i]，又因为F单调递增，所以F[j-1]+max[j..i]<=F[j]+max[j+1.i]，即决策(j-1)一定不比决策j差，也就是决策j不可能成为最优决策。
这样，可以维护一个下标严格递增、A值严格递减的队列Q（即对于队列中的任意两个元素Q[i]和Q[j]，若i<j，则Q[i].pos<Q[j].pos且A[Q[i].pos]>A[Q[j].pos]，具体实现时pos可省略）。则可能成为最优决策的决策要么是在这个队列Q里，要么是B[i]。对于队列中的某个决策Q[x]，该决策导出的值为F[Q[x]]+A[Q[x + 1]]（很容易证明max[Q[x]+1..i]=A[Q[x + 1]]），找到这些导出的值中的最小值即可（注意，队尾元素没有导出值）。对于决策B[i]，只需要在预处理的时候同时得到MAX[i]=max[B[i]+1..i]即可（也可以在O(N)时间内得到），决策B[i]导出的值为F[B[i]]+MAX[i]。
在删除队首过时元素的时候，需要把导出值也删除，删除队尾元素也一样，插入的时候，若插入前队列不为空，则需要插入一个导出值。也就是，需要一个支持在对数时间内进行插入、删除任意结点、找最小值等操作，显然用平衡树最好。
注意事项：
（1）不管是在队首删除还是在队尾删除，若删除的是队列中的最后一个元素，则不需要在平衡树中删除导出值；
（2）插入时，若插入前队列为空，则不需要在平衡树中插入导出值；
（3）在计算F[i]时，应先将决策i压入。
代码：
#include <iostream>
#include <stdio.h>
using namespace std;
#define re1(i, n) for (int i=1; i<=n; i++)
const int MAXN = 100001;
struct node {
int l, r, p, sz0, sz, mul;
long long v;
} T[MAXN];
const long long INF = ~0Ull >> 2;
int n, N = 0, a[MAXN], b[MAXN], MAX[MAXN], Q[MAXN], front = 0, rear = -1, root = 0;
long long m, F[MAXN], res = 0;
void init()
{
cin >> n >> m;
re1(i, n) scanf("%d", &a[i]); a[0] = ~0U >> 2;
}
void prepare()
{
re1(i, n) if (a[i] > m) {res = -1; return;}
int x = 1;
long long sum = 0;
re1(i, n) {
for (sum+=a[i]; sum>m; sum-=a[x++]) ;
b[i] = x - 1;
}
re1(i, n) {
for (; front<=rear && Q[front]<=b[i]; front++) ;
for (; front<=rear && a[Q[rear]]<=a[i]; rear--) ;
Q[++rear] = i; MAX[i] = a[Q[front]];
}
}
void vst(int x)
{
if (x) {
cout << T[x].v << ' ';
vst(T[x].l); vst(T[x].r);
}
}
void slc(int _p, int _c)
{
T[_p].l = _c; T[_c].p = _p;
}
void src(int _p, int _c)
{
T[_p].r = _c; T[_c].p = _p;
}
void upd(int x)
{
T[x].sz0 = T[T[x].l].sz0 + T[T[x].r].sz0 + T[x].mul;
T[x].sz = T[T[x].l].sz + T[T[x].r].sz + 1;
}
void lrot(int x)
{
int y = T[x].p;
if (y == root) T[root = x].p = 0; else {int p = T[y].p; if (y == T[p].l) slc(p, x); else src(p, x);}
src(y, T[x].l); slc(x, y); T[x].sz0 = T[y].sz0; T[x].sz = T[y].sz; upd(y);
}
void rrot(int x)
{
int y = T[x].p;
if (y == root) T[root = x].p = 0; else {int p = T[y].p; if (y == T[p].l) slc(p, x); else src(p, x);}
slc(y, T[x].r); src(x, y); T[x].sz0 = T[y].sz0; T[x].sz = T[y].sz; upd(y);
}
void maintain(int x, bool ff)
{
int z;
if (ff) {
if (T[T[T[x].r].r].sz > T[T[x].l].sz) {z = T[x].r; lrot(z);}
else if (T[T[T[x].r].l].sz > T[T[x].l].sz) {z = T[T[x].r].l; rrot(z); lrot(z);} else return;
} else {
if (T[T[T[x].l].l].sz > T[T[x].r].sz) {z = T[x].l; rrot(z);}
else if (T[T[T[x].l].r].sz > T[T[x].r].sz) {z = T[T[x].l].r; lrot(z); rrot(z);} else return;
}
maintain(T[z].l, 0); maintain(T[z].r, 1); maintain(z, 0); maintain(z, 1);
}
int find(long long _v)
{
int i = root;
long long v0;
while (i) {
v0 = T[i].v;
if (_v == v0) return i; else if (_v < v0) i = T[i].l; else i = T[i].r;
}
return 0;
}
int Find_Kth(int K)
{
int i = root, s0, m0;
while (1) {
s0 = T[T[i].l].sz0; m0 = T[i].mul;
if (K <= s0) i = T[i].l; else if (K <= s0 + m0) return i; else {K -= s0 + m0; i = T[i].r;}
}
}
void ins(long long _v)
{
if (!root) {
T[++N].v = _v; T[N].l = T[N].r = T[N].p = 0; T[N].sz0 = T[N].sz = T[N].mul = 1; root = N;
} else {
int i = root, j;
long long v0;
while (1) {
T[i].sz0++; v0 = T[i].v;
if (_v == v0) {T[i].mul++; return;} else if (_v < v0) j = T[i].l; else j = T[i].r;
if (j) i = j; else break;
}
T[++N].v = _v; T[N].l = T[N].r = 0; T[N].sz0 = T[N].sz = T[N].mul = 1; if (_v < v0) slc(i, N); else src(i, N);
while (i) {T[i].sz++; maintain(i, _v > T[i].v); i = T[i].p;}
}
}
void del(int x)
{
if (T[x].mul > 1) {
T[x].mul--; while (x) {T[x].sz0--; x = T[x].p;}
} else {
int l = T[x].l, r = T[x].r, p;
if (l && r) {
int y; while (y = T[l].r) l = y;
T[x].v = T[l].v; T[x].mul = T[l].mul; p = T[l].p;
if (l == T[p].l) slc(p, T[l].l); else src(p, T[l].l);
while (p) {upd(p); p = T[p].p;}
} else {
if (x == root) T[root = l + r].p = 0; else {p = T[x].p; if (x == T[p].l) slc(p, l + r); else src(p, l + r); while(p) {upd(p); p = T[p].p;}}
}
}
}
long long h(int x)
{
return F[Q[x]] + a[Q[x + 1]];
}
void solve()
{
F[0] = 0; front = 0; rear = 0; Q[0] = 0;
re1(i, n) {
for (; front<=rear && Q[front]<b[i];) {if (front < rear) del(find(h(front))); front++;}
for (; front<=rear && a[Q[rear]]<=a[i];) {if (front < rear) del(find(h(rear - 1))); rear--;}
Q[++rear] = i; if (front < rear) ins(h(rear - 1));
if (root) F[i] = T[Find_Kth(1)].v; else F[i] = INF;
if (F[b[i]] + MAX[i] < F[i]) F[i] = F[b[i]] + MAX[i];
}
res = F[n];
}
void pri()
{
cout << res << endl;
}
int main()
{
init();
prepare();
if (!res) solve();
pri();
return 0;
}