记录编号	586881	评测结果	AAAAAAAAAA
题目名称	[APIO2014]序列分割	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	2.638 s
提交时间	2024-03-01 21:37:06	内存使用	57.87 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//斜率优化 
const int N = 1e5+10;
int n,k,now,l,r;
ll s[N],f[N][2];
int q[N],la[N][210];
ll X(int a){return s[a];}
ll Y(int a){return f[a][now^1] - s[a] * s[a];}
double slope(int a,int b){
	if(X(a) == X(b))return 1e18;//极大值直接去掉 
	return (double)(Y(a) - Y(b)) / (X(a) - X(b));
}
void prin(int x,int y){
	if(!x)return;
	prin(la[x][y],y-1);
	if(x != n)printf("%d ",x);
}
int main(){
	freopen("sequencesegmentation.in","r",stdin);
	freopen("sequencesegmentation.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i = 1;i <= n;i++)scanf("%lld",&s[i]),s[i] += s[i-1];
	for(int t = 1;t <= k;t++){
		int l = 1,r = 0;
		for(int i = 1;i <= n;i++){
			while(l < r && slope(q[l],q[l+1]) >= -s[i])l++;
			if(l <= r){
				int j = q[l];la[i][t] = j;
				f[i][now] = f[j][now^1] + s[j] * (s[i] - s[j]);
			}
			while(l < r && slope(q[r-1],q[r]) <= slope(q[r],i))r--;
			q[++r] = i;
		} 
		now ^= 1;
	}
	printf("%lld\n",f[n][now^1]);

	return 0;
	
}