记录编号	592691	评测结果	AAAAAAAA
题目名称	[ZJOI 2007] 仓库建设	最终得分	100
用户昵称	qyd	是否通过	通过
代码语言	C++	运行时间	0.791 s
提交时间	2024-07-29 16:05:28	内存使用	6.58 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000010;
int n,x[maxn],p[maxn],c[maxn];
ll sump[maxn],sumxp[maxn];
int head,tail,q[maxn],f[maxn];
ll b(int i){return f[i]-x[i]*p[i]-c[i]+sumxp[i];}
ll y(int i){return f[i]+sumxp[i];}
ll k(int i){return x[i];}
ll xx(int i){return sump[i];}
double slope(int i,int j){return 1.0*(y(j)-y(i))/(xx(j)-xx(i));}
int main()
{
	freopen("storage.in","r",stdin);
	freopen("storage.out","w",stdout);
	cin>>n;
	sump[0]=0;sumxp[0]=0;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>p[i]>>c[i];
		sump[i]=sump[i-1]+p[i];
		sumxp[i]=sumxp[i-1]+x[i]*p[i];
	}
	head=1;tail=1;q[0]=0;
	for(int i=1;i<=n;i++)
	{
		while(head<tail&&slope(q[head],q[head+1])<x[i])head++;
		int j=q[head];
		f[i]=f[j]+sumxp[j]-x[i]*sump[j]+x[i]*sump[i]+c[i]-sumxp[i];
		while(head<tail&&slope(q[tail-1],q[tail])>slope(q[tail-1],i))tail--;
		q[++tail]=i; 
	}
	cout<<f[n]<<endl;
	return 0;
}