Description
机器上有N个需要处理的任务，它们构成了一个序列。这些任务被标号为1到N，因此序列的排列为1,2,3…N。这N个任务被分成若干批，每批包含相邻的若干任务。从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是Ti。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和。注意，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案，使得总费用最小。
Input 第一行两个整数，N,S。 接下来N行每行两个整数，Ti,Fi。 Output 一个整数，为所求的答案。
考虑裸的dp方程dp[i]=min{dp[j]+st[i] * (sf[i]-sf[j])+S * (sf[n]-sf[j])}
其中dp[i]表示完成前i个任务的最小花费，st和sf是前缀和。
变形得到dp[j]-S * sf[j]=st[i] * sf[j]+dp[i]-st[i] * sf[i]-S * sf[n]
因为st不单调，而sf单调，所以可以在末端插入并维护下凸壳，每次二分查找需要的斜率。
#include<cstdio>
#include<cstring>
#define LL long long
const double oo=1e17;
int n,que[300010];
LL S,dp[300010],g[300010],t[300010],f[300010],st[300010],sf[300010];
LL rd()
{LL x=0;int f=1;char c=getchar();while ((c<'0'||c>'9')&&c!='-') c=getchar();if (c=='-'){f=-1;c=getchar();}while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
double tj(int x,int y)
{if (sf[x]==sf[y]) return oo;return (double)(g[y]-g[x])/(sf[y]-sf[x]);
}
int main()
{int i,j,k,p,q,x,y,z,top,l,r,mid;scanf("%d%lld",&n,&S);for (i=1;i<=n;i++){t[i]=rd();f[i]=rd();st[i]=st[i-1]+t[i];sf[i]=sf[i-1]+f[i];}top=1;for (i=1;i<=n;i++){l=1;r=top;while (l<r){mid=(l+r+1)/2;if (tj(que[mid-1],que[mid])<=st[i]) l=mid;else r=mid-1;}dp[i]=dp[que[l]]+st[i]*(sf[i]-sf[que[l]])+S*(sf[n]-sf[que[l]]);g[i]=dp[i]-S*sf[i];while (top>1&&tj(que[top-1],que[top])>=tj(que[top],i)) top--;que[++top]=i;}printf("%lld\n",dp[n]);
}