33分 评测记录

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int n,m,f[210][N],sum[N],ans,g[210][N];
int x(int i){return sum[i];}
int y(int k,int i){return f[k-1][i]-sum[i]*sum[i];}
void print(int k,int x)
{
	if(g[k-1][x])print(k-1,g[k-1][x]);
	cout<<x<<" ";
}
signed main(){
	/*f[k][i]=f[k-1][j]+sum[j]*(sum[i]-sum[j]);
	f[k][i]=f[k-1][j]+sum[j]*sum[i]-sum[j]*sum[j];
	f[k-1][j]-sum[j]*sum[j]=f[k][i]-sum[j]*sum[i];*/
	cin>>n>>m;
	int o;
	for(int i=1;i<=n;i++)cin>>o,sum[i]=sum[i-1]+o; 
	for(int k=1;k<=m;k++)
	{
		int q[N],l=1,r=1;
		q[1]=0;
		for(int i=1;i<=n;i++)
		{
			while(l<r&&y(k,q[l])-y(k,q[l+1])<=sum[i]*(x(q[l+1])-x(q[l])))l++;
			f[k][i]=f[k-1][q[l]]+sum[q[l]]*(sum[i]-sum[q[l]]);
			g[k][i]=q[l];
			while(l<r&&(y(k,q[r-1])-y(k,q[r]))*(x(i)-x(r))<=(y(k,i)-y(k,q[r]))*(x(q[r])-x(q[r-1])))r--;
			q[++r]=i;
		}
	}
	cout<<f[m][n]<<endl;
	print(m,g[m][n]);
	return 0;
}