//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 的格式要求是 "插入 [该代码片段的中文名]"

{
    "二分 斜率优化   (x单调 k不单调)": {
        "prefix": "acm-5.1任务安排3",
        "body": [
            "#include<cstring>",
            "#include<cstdio>",
            "#define LL long long",
            "#define Re register LL",
            "const int N=3e5+5;",
            "LL i,j,n,h=1,t=0,S,Q[N],ST[N],SF[N],dp[N];",
            "//dp[p][i]=min(dp[p-1][j]+(ST[i]+S*p)*(SF[i]-SF[j]));",
            "//dp[i]=dp[j]+ST[i]*(SF[i]-SF[j])+S*(SF[n]-SF[j]);",
            "//(S+ST[i]) * SF[j] + (dp[i]-ST[i]*SF[i]-S*SF[i]) = (dp[j])",
            "//    k     *   x   +              b              = y",
            "//ti� 均>0，且ST[i]是单调递增",
            "inline LL min(Re a,Re b){return a<b?a:b;}",
            "inline LL X(Re j){return SF[j];}",
            "inline LL Y(Re j){return dp[j];}",
            "inline long double slope(Re i,Re j){return X(j)==X(i)?(Y(j)>=Y(i)?1e18:-1e18):(long double)(Y(j)-Y(i))/(X(j)-X(i));}",
            "inline LL sakura(Re k){",
            "\tif(h==t)return Q[h];",
            "\tRe l=h,r=t;",
            "\twhile(l<r){",
            "\t\tRe mid=l+r>>1,i=Q[mid],j=Q[mid+1];",
            "\t\tif(slope(i,j)<k)l=mid+1;",
            "\t\telse r=mid;",
            "\t}",
            "\treturn Q[l];",
            "}",
            "int main(){",
            "    scanf(\"%lld%lld\",&n,&S);",
            "    for(i=1;i<=n;ST[i]+=ST[i-1],SF[i]+=SF[i-1],++i)scanf(\"%lld%lld\",&ST[i],&SF[i]);",
            "    Q[++t]=0;",
            "\tfor(i=1;i<=n;++i){",
            "\t\tj=sakura(S+ST[i]);",
            "        dp[i]=dp[j]+ST[i]*(SF[i]-SF[j])+S*(SF[n]-SF[j]);",
            "        while(h<t&&slope(Q[t-1],Q[t])>=slope(Q[t-1],i))--t;",
            "        Q[++t]=i;",
            "\t}",
            "    printf(\"%lld\",dp[n]);",
            "}",
            ""
        ],
        "description": "插入 二分 斜率优化   (x单调 k不单调)"
    }
}