//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "序列分割": {
        "prefix": "acm-5.1max",
        "body": [
            "#include<cstring>",
            "#include<cstdio>",
            "#define LL long long",
            "#define Re register LL",
            "const int N=1e5+5,M=205;",
            "LL tmp,i,j,p,n,K,h,t,Q[N],S[N],to[M][N],dp[M][N];",
            "inline LL max(Re a,Re b){return a>b?a:b;}",
            "//dp[p][i]=dp[p-1][j]+S[j]*(S[i]-S[j])",
            "//(S[i]) * S[j] + (-dp[p][i]) = (S[j]^2-dp[p-1][j])",
            "//  k    *  x   +       b     =          y",
            "inline LL X(Re j){return S[j];}",
            "inline LL Y(Re j){return S[j]*S[j]-dp[p-1][j];}",
            "inline long double slope(Re i,Re j){return X(j)==X(i)?-1e18:(long double)(Y(j)-Y(i))/(X(j)-X(i));}",
            "int main(){",
            "    scanf(\"%lld%lld\",&n,&K);",
            "    for(i=1;i<=n;S[i]+=S[i-1],++i)scanf(\"%lld\",&S[i]);",
            "    for(p=1;p<=K;++p){",
            "        h=1,t=0,Q[++t]=p-1;",
            "        for(i=p;i+K-p<=n;++i){",
            "            while(h<t&&slope(Q[h],Q[h+1])<S[i])++h;",
            "        \tdp[p][i]=dp[p-1][to[p][i]=j=Q[h]]+S[j]*(S[i]-S[j]);",
            "       \t\twhile(h<t&&slope(Q[t-1],Q[t])>slope(Q[t-1],i))--t;",
            "        \tQ[++t]=i;",
            "        }",
            "    }",
            "    printf(\"%lld\\n\",dp[K][n]);",
            "    for(i=n,j=K;j>=1;--j)printf(\"%lld \",i=to[j][i]);",
            "}",
            ""
        ],
        "description": "插入 序列分割"
    }
}