记录编号	359365	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2007] 仓库建设	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.348 s
提交时间	2016-12-22 13:44:01	内存使用	38.44 MiB

#include<cstdio>
typedef long long ll;
const int N=1e6+10;
int n,x[N],p[N],c[N],q[N],head,tail;
ll sump[N],sumpx[N],dp[N];
double K(int j,int k){
	return 1.0*(dp[k]+sumpx[k]-dp[j]-sumpx[j])/(sump[k]-sump[j]);
}
int main()
{
	freopen("storage.in","r",stdin);
	freopen("storage.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d%d%d",&x[i],&p[i],&c[i]);
		sump[i]=sump[i-1]+p[i];
		sumpx[i]=sumpx[i-1]+(ll)p[i]*x[i];
	}
	head=tail=1;q[1]=0;
	for (int i=1;i<=n;i++){
		for (;head<tail&&K(q[head],q[head+1])<x[i];head++);
		int k=q[head];
		dp[i]=dp[k]+c[i]-(sumpx[i]-sumpx[k])+(sump[i]-sump[k])*x[i];
		for (;head<tail&&K(q[tail-1],q[tail])>K(q[tail],i);tail--);
		q[++tail]=i;
	}
	printf("%lld\n",dp[n]);
	return 0;
}