//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.1min",
        "body": [
            "#include<cstdio>",
            "#define Re register int",
            "const int N=4e6+105;",
            "int i,j,n,m,h=1,t=0,T,ti,ans=2e9,G[N],S[N],Q[N],dp[N];",
            "inline int min(Re a,Re b){return a<b?a:b;}",
            "//                 i",
            "//                 k=j+1",
            "//dp[i]=dp[j]+(G[i]-G[j])*i-(S[i]-S[j])",
            "//(i) * G[j] + (dp[i]+S[j]-i*G[i]) = (dp[j]+S[j])",
            "// k  *  x   +          b          =      y",
            "inline int X(Re j){return G[j];}",
            "inline int Y(Re j){return dp[j]+S[j];}",
            "inline long double slope(Re i,Re j){return X(i)==X(j)?(Y(j)>Y(i)?2e9:-2e9):(long double)(Y(j)-Y(i))/(long double)(X(j)-X(i));}",
            "int main(){",
            "    scanf(\"%d%d\",&n,&m);",
            "    for(i=1;i<=n;T=-min(-T,-ti),++G[ti],S[ti]+=ti,++i)scanf(\"%d\",&ti);",
            "    for(i=1;i<T+m;++i)G[i]+=G[i-1],S[i]+=S[i-1];",
            "    for(i=0;i<m;++i)dp[i]=G[i]*i-S[i];",
            "    Q[++t]=0;",
            "    for(i=m;i<T+m;++i){",
            "    \twhile(h<t&&slope(Q[h],Q[h+1])<=i)++h;",
            "        dp[i]=dp[j=Q[h]]+(G[i]-G[j])*i-S[i]+S[j];",
            "       \twhile(h<t&&slope(Q[t-1],Q[t])>=slope(Q[t-1],i-m+1))--t;",
            "        Q[++t]=i-m+1;//(j+1)+m<=i",
            "\t}",
            "    for(i=T;i<T+m;++i)ans=min(ans,dp[i]);",
            "    printf(\"%d\",ans);",
            "}",
            ""
        ],
        "description": "插入 摆渡车"
    }
}