代码：

#include<iostream>
#include<vector>
#include<deque>
using namespace std;
struct Data {
	long long f, s,position;
};
deque<Data>que;
vector<long long>prefixSum_A;
vector<long long>DP[2];
vector<vector<long long>>record[2];
vector<long long>F;
int N, K;
bool JudgeFront(const long long&Si) {
	if (que.size() == 1) {
		return 0;
	} else {
		Data node1 = que.front();
		que.pop_front();
		Data node2 = que.front();
		que.push_front(node1);
		if(node2.s==node1.s)
			return 1;
		if ((node2.f - node1.f) / (node1.s - node2.s) <= Si)
			return 1;
		else
			return 0;
	}
}
bool JudgeBack(const Data add) {
	if (que.size() == 1) {
		return 0;
	} else {
		Data node1 = que.back();
		que.pop_back();
		Data node2 = que.back();
		que.push_back(node1);
		if(add.s==node1.s)
			return 1;
		if(node1.s==node2.s)
			return 0;
		if ((node1.f - node2.f) / (node1.s - node2.s)
		    >= (add.f - node1.f) / (add.s - node1.s))
			return 1;
		else
			return 0;
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> K;
	F.assign(N + 1, 0);
	DP[0].assign(N + 1, 0);
	record[0].assign(N+1,{0});
	record[1].assign(N+1,{0});
	DP[1].assign(N + 1, 0);
	prefixSum_A.assign(N + 1, 0);
	record[1][0].clear();
	record[0][0].clear();
	for (int i = 1; i <= N; i++) {
		int A;
		cin >> A;
		prefixSum_A[i] = prefixSum_A[i - 1] + A;
		record[1][i].clear();
		record[0][i].clear();
	}
	for (int sectionSum = 1; sectionSum <= K; sectionSum++) {
		int j_now = sectionSum % 2;
		int j_before = (sectionSum - 1) % 2;
		DP[j_now].assign(N+1,0);
		for (int i = 1; i <= N; i++)
			F[i] = DP[j_before][i] - prefixSum_A[N] * prefixSum_A[i];
		que.push_back({F[sectionSum-1], prefixSum_A[sectionSum-1],sectionSum-1});
		for (int i = sectionSum; i <= N; i++) {
			while (que.empty() == 0 && JudgeFront(prefixSum_A[i]))
				que.pop_front();
			DP[j_now][i] = que.front().f - prefixSum_A[i] * prefixSum_A[i] +
			               prefixSum_A[i] * que.front().s
			               + prefixSum_A[i] * prefixSum_A[N];
			record[j_now][i]=record[j_before][que.front().position];
			record[j_now][i].push_back(i);
			while (que.empty() == 0 && JudgeBack({F[i], prefixSum_A[i],i}))
				que.pop_back();
			que.push_back({F[i], prefixSum_A[i],i});
		}
		que.clear();
	}
	long long Ans=0,p=0;
	for(int i=1;i<=N;i++)
		if(Ans<DP[K%2][i]){
			Ans=DP[K%2][i];
			p=i;
		}
	cout<<Ans<<"\n";	
	for(int i=0,length=record[K%2][p].size();i<length;i++){
		cout<<record[K%2][p][i]<<" ";
	}
	return 0;
}

测试记录