乍一看这是斜率优化模板题，然而……

注意到总大小大于 $\dfrac{M}{2}$ 时再合并一定不优，因此直接 $O(NM)$ 也能 AC。

#include <bits/stdc++.h>
using namespace std;
long long dp[100012], w[100012];
int main()
{
	int n, m;
	while (cin >> n >> m)
	{
		for (int i = 0; i <= n; i++)
			dp[i] = 1e18;
		dp[0] = 0;
		for (int i = 1; i <= n; i++)
		{
			cin >> w[i];
			w[i] += w[i - 1];
		}
		for (int i = 1; i <= n; i++)
			for (int j = i - 1; j >= 0 && w[i] - w[j] <= 1000; j--)
				dp[i] = min(dp[i], dp[j] + m + (w[i] - w[j]) * (w[i] - w[j]));
		cout << dp[n] << endl;
	}
	return 0;
}