大概只能过n=1000

# include <bits/stdc++.h>
# define int long long
# define val(x, id) (lne[x].k * pre[id] + lne[x].b)
# define l(id) tr[id].l
# define r(id) tr[id].r
# define iminn(id) tr[id].iminn
# define cp(a, b, c) (val(a, c) == val(b, c) ? (lne[a].num > lne[b].num ? a : b) : (val(a, c) < val(b, c) ? a : b))
using namespace std;

struct lines
{
	int k, b, num;
} lne[100005];//(pre[i] - pre[j]) ^ 2 = pre[i] ^ 2 - 2 * pre[i] * pre[j + 1] + pre[j] * 2
struct segment
{
	int l, r, iminn;
} tr[400005];
int n, m, x[100005], dp[100005], pre[100005], num[100005];

void build(int id, int l, int r)
{
	tr[id] = {l, r, 0};
	if (l == r)
		return;
	int mid = (l + r) / 2;
	build(2 * id, l, mid);
	build(2 * id + 1, mid + 1, r);
}

void upd_cover(int id, int x)
{
	if (l(id) == r(id))
	{
		iminn(id) = cp(iminn(id), x, l(id));
		return;
	}
	if (cp(iminn(id), x, l(id)) == x && cp(iminn(id), x, r(id)) == x)
	{
		iminn(id) = x;
		return;
	}
	if (cp(iminn(id), x, l(id)) == iminn(id) && cp(iminn(id), x, r(id)) == iminn(id))
		return;
	if (cp(iminn(id), x, r(2 * id)) == x)
		swap(x, iminn(id));
	if (cp(iminn(id), x, l(id)) == x)
		upd_cover(2 * id, x);
	else
		upd_cover(2 * id + 1, x);
}

int query(int id, int x)
{
	if (l(id) == r(id))
		return iminn(id);
	if (x > r(2 * id))
		return cp(query(2 * id + 1, x), iminn(id), x);
	else
		return cp(query(2 * id, x), iminn(id), x);
}

bool check(int k)
{
	build(1, 1, n);
	for (int i = 1; i <= n; ++i)
	{
		int x = query(1, i);
		num[i] = lne[x].num + 1;
		dp[i] = val(x, i) + pre[i] * pre[i] + k;
		lne[i] = {-2 * pre[i], dp[i] + pre[i] * pre[i], num[i]};
		upd_cover(1, i);
	}
	return num[n] >= m;
}

signed main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		cin >> x[i];
		pre[i] = pre[i - 1] + x[i];
	}
	if (m == 1)
	{
		cout << pre[n] * pre[n] + 2 * pre[n] + 1 << endl;
		return 0;
	}
	int l = 0, r = 1000000000000;
	while (r - l > 1)
	{
		int mid = (l + r) / 2;
		if (check(mid))
			l = mid;
		else
			r = mid;
	}
	check(l);
	cout << dp[n] - m * l + 2 * pre[n] + m << endl;
	return 0;
}