记录编号	423329	评测结果	AAAAAAAA
题目名称	[ZJOI 2007] 仓库建设	最终得分	100
用户昵称	sherlockm	是否通过	通过
代码语言	C++	运行时间	0.611 s
提交时间	2017-07-11 16:20:04	内存使用	38.46 MiB

#include <bits/stdc++.h>
using namespace std;

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
const int maxn = 1000050;
typedef long long ll;

int n, pos[maxn], p[maxn], c[maxn];
ll f[maxn], g[maxn], sum[maxn];
int st[maxn], top;

void read(int &x){x=0;char c='.';while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();}
ll calc(int j,int i){return -sum[j]*pos[i]+f[j]+g[j];}
double sect(int i,int j)
{
	ll b1 = f[i]+g[i], b2 = f[j]+g[j];
	ll k1 = -sum[i], k2 = -sum[j];
	return (double)(b2-b1)/(k1-k2);
}
int main()
{
	freopen("storage.in","r",stdin);
	freopen("storage.out","w",stdout);
	read(n); 
	fo(i,1,n) read(pos[i]), read(p[i]), read(c[i]);
	fo(i,1,n) {g[i] = g[i-1] + (ll)p[i]*pos[i]; sum[i] = sum[i-1] + p[i];}
	st[++top] = 0;
	fo(i,1,n)
	{
		int l = 1, r = top, j, mid;
		while(l <= r)
		{
			mid = l + r >> 1;
			if(mid == 1 || sect(st[mid],st[mid-1])<=pos[i])
				j = mid, l = mid + 1;
			else
				r = mid - 1;
		}
		f[i] = calc(st[j],i)+sum[i-1]*pos[i]-g[i-1]+c[i];
		while(top>1 && sect(i,st[top]) <= sect(st[top],st[top-1])) -- top;
		st[++top] = i;
	}
	printf("%lld\n",f[n]);
	return 0;
}