仓库建设[ZJOI2007]

#include <bits/stdc++.h>
#define N 1000005
using namespace std;
typedef long long ll;

template <typename T>
inline void read(T &num) {
	T x = 0, f = 1; char ch = getchar();
	for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
	num = x * f;
}

int n, head, tail, q[N];
ll a[N], p[N], c[N], dp[N], sum[N], sum2[N], K[N];

inline ll getx(int id) {
	return sum[id];
}
inline ll gety(int id) {
	return dp[id] + sum2[id];
}
inline double slope(int x, int y) {
	return getx(x) == getx(y) ? 1e15 : 1.0 * (gety(x) - gety(y)) / (getx(x) - getx(y));
}

int main() {
	read(n);
	for (int i = 1; i <= n; i++) {
		read(a[i]); read(p[i]); read(c[i]);
		sum[i] = sum[i-1] + p[i];
		sum2[i] = sum2[i-1] + a[i] * p[i];
		K[i] = a[i];
	}
	q[head=tail=1] = 0;
	for (int i = 1; i <= n; i++) {
		while (head < tail && slope(q[head], q[head+1]) < K[i]) head++;
		int j = q[head];
		dp[i] = dp[j] + a[i] * (sum[i] - sum[j]) - (sum2[i] - sum2[j]) + c[i];
		while (head < tail && slope(q[tail-1], q[tail]) > slope(q[tail], i)) tail--;
		q[++tail] = i;
	}
	printf("%lld\n", dp[n]);
	return 0;
}