记录编号	452585	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	2073.有趣的有趣的家庭菜园	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	5.948 s
提交时间	2017-09-19 20:49:54	内存使用	28.17 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
#define MAXN 100010
#define lc rt<<1
#define rc rt<<1|1
#define INF 1<<64-1
namespace IO {
	char buf[1 << 15], *fs, *ft;
	inline char gc() { return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 15, stdin), fs == ft)) ? 0 : *fs++; }
	inline int qr() {
		int x = 0, rev = 0, ch = gc();
		while (ch<'0' || ch>'9') { if (ch == '-')rev = 1; ch = gc(); }
		while (ch >= '0'&&ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = gc(); }
		return rev ? -x : x;
	}
}using namespace IO;
using namespace std;
LL f[MAXN], g[MAXN];//前i个数递增排且必须选最后一个的最大收益
LL t[MAXN << 4], lazy[MAXN << 4];
void Up(int rt) { t[rt] = max(t[lc], t[rc]); }
void Down(int rt) {
	if (!lazy[rt])return;
	t[lc] += lazy[rt]; t[rc] += lazy[rt];
	lazy[lc] += lazy[rt]; lazy[rc] += lazy[rt];
	lazy[rt] = 0;
}
void Build(int l, int r, int rt) {
	t[rt] = 0; lazy[rt] = 0;
	if (l == r)return;
	int mid = l + r >> 1;
	Build(l, mid, lc); Build(mid + 1, r, rc);
	Up(rt);
}
LL Max(int L, int R, int l, int r, int rt) {
	if (L <= l&&R >= r)return t[rt];
	int mid = l + r >> 1; LL res = -INF;
	Down(rt);
	if (L <= mid)res = Max(L, R, l, mid, lc);
	if (R>mid)res = max(res, Max(L, R, mid + 1, r, rc));
	return res;
}
void Add(int L, int R, int l, int r, int rt, LL x) {
	if (L <= l&&R >= r) { t[rt] += x; lazy[rt] += x; return; }
	int mid = l + r >> 1;
	Down(rt);
	if (L <= mid)Add(L, R, l, mid, lc, x);
	if (R>mid)Add(L, R, mid + 1, r, rc, x);
	Up(rt);
}
void Change(int p, int l, int r, int rt, LL x) {
	if (l == r) { t[rt] = max(t[rt], x); return; }
	int mid = l + r >> 1;
	Down(rt);
	if (p <= mid)Change(p, l, mid, lc, x);
	else Change(p, mid + 1, r, rc, x);
	Up(rt);
}
int N, h[MAXN], p[MAXN], c[MAXN], temp[MAXN], cnt, ne[MAXN];
int main() {
	freopen("Fgarden.in", "r", stdin);
	freopen("Fgarden.out", "w", stdout);
	N = qr();
	for (int i = 1; i <= N; i++) { h[i] = qr(); p[i] = qr(); c[i] = qr(); temp[i] = h[i]; }
	sort(temp + 1, temp + 1 + N);
	for (int i = 1; i <= N; i++) { if (temp[i] != temp[i - 1])ne[++cnt] = temp[i]; }
	for (int i = 1; i <= N; i++)h[i] = lower_bound(ne + 1, ne + 1 + cnt, h[i]) - ne;
	Build(1, cnt, 1);
	//f[1] = p[1];
	//Change(h[1], 1, cnt, 1, f[1]);
	for (int i = 1; i <= N; i++) {
		f[i] = p[i] + Max(1, h[i], 1, cnt, 1);
		Add(1, h[i], 1, cnt, 1, -c[i]);
		Change(h[i], 1, cnt, 1, f[i]);
	}
	Build(1, cnt, 1);
	//g[N] = p[N];
	//Change(h[N], 1, cnt, 1, f[N]);
	for (int i = N; i >= 1; i--) {
		g[i] = p[i] + Max(1, h[i], 1, cnt, 1);
		Add(1, h[i], 1, cnt, 1, -c[i]);
		Change(h[i], 1, cnt, 1, g[i]);
	}
	LL ans = 0;
	for (int i = 1; i <= N; i++)ans = max(ans, f[i] + g[i] - p[i]);
	printf("%lld", ans);
	return 0;
}