有三个点TLE了……

#include<bits/stdc++.h>
#define ld long double
#define ll long long
using namespace std;
const int N=1e5+5;
int n,k,a[N];
int read(){
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
void print(ll x){
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
ll sum[N],dp[N][205],q[N],head,tail,solve[N][205];
ld X(int x){return sum[x];}
ld Y(int x,int d){return dp[x][d];}
ld slope(int x,int y,int d){return (Y(x,d)-Y(y,d))/(X(x)-X(y)+(X(x)==X(y)?1e-9:0));}
ll calc(int x,int y,int d){return dp[x][d]+(sum[y]-sum[x])*(sum[n]-sum[y]);}
int main(){
	n=read(),k=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
	for(int i=1;i<n;i++) dp[i][1]=sum[i]*(sum[n]-sum[i]);
	for(int j=2;j<=k;j++){
		head=1,tail=1;
		q[1]=j-1;
		for(int i=j;i<n;i++){
			while(head<tail&&slope(q[head+1],q[head],j-1)>=sum[n]-sum[i]) head++;
			dp[i][j]=calc(q[head],i,j-1);
			solve[i][j]=q[head];
			while(head<tail&&slope(q[tail],q[tail-1],j-1)<=slope(i,q[tail],j-1)) tail--;
			q[++tail]=i;
		}
	}
	int p=k;
	for(int i=k;i<n;i++) if(dp[i][k]>dp[p][k]) p=i;
	print(dp[p][k]);putchar('\n');
	for(int i=k;i>=1;i--){
		print(p);putchar(' ');
		p=solve[p][i];
	}
	return 0;
}