萌新求助

#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
#define ll long long
#define For(i,x,y) for (register int i=(x);i<=(y);i++)
#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)
#define cross(i,k) for (register int i=first[k];i;i=last[i])
inline ll read(){
    ll x=0;int ch=getchar(),f=1;
    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
    if (ch=='-'){f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
const int N = 1e5+10;
int n,m,h,t,q[N],next[210][N],cnt,ans[N];
ll sum[N],dp[N],last[N],x[N],y[N];
inline void dfs(int i,int j){
    if (i>0) dfs(i-1,next[i][j]);
    ans[++cnt]=j;
}
int main(){
    n=read(),m=read();
    For(i,1,n) sum[i]=sum[i-1]+read();
    For(j,1,m){
        h=t=1,q[1]=j,x[j]=sum[j],y[j]=last[j]-sum[j]*sum[j];
        For(i,j+1,n){
            while (h<t&&y[q[h+1]]-y[q[h]]>(-sum[i])*(x[q[h+1]]-x[q[h]])) h++;
            dp[i]=last[q[h]]+(sum[i]-sum[q[h]])*sum[q[h]],next[j][i]=q[h];
            x[i]=sum[i],y[i]=last[i]-sum[i]*sum[i];
            while (h<t&&(y[q[t]]-y[q[t-1]])*(x[i]-x[q[t]])<(y[i]-y[q[t]])*(x[q[t]]-x[q[t-1]])) t--;
            q[++t]=i;
        }
        For(i,1,n) last[i]=dp[i];
    }
    printf("%lld\n",dp[n]),dfs(m,n);
    For(i,1,m) printf("%d ",ans[i]);
}