记录编号	410935	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	有趣的有趣的家庭菜园	最终得分	100
用户昵称	asd	是否通过	通过
代码语言	C++	运行时间	9.988 s
提交时间	2017-06-02 23:10:36	内存使用	36.94 MiB

    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #define fo(i,a,b) for(i=a;i<=b;i++)
    #define fod(i,a,b) for(i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const int maxn=100007;
    int i,j,k,l,n,m;
    ll tt,ans;
    ll a[maxn],b[maxn],c[maxn],d[maxn],tot;
    ll f[maxn],g[maxn];
    struct nod {
    	ll a,d;
    } e[maxn];
    struct node {
    	ll da,biao,biao1,biao2;
    } t[maxn*10];
    bool cmp(nod x,nod y) {
    	return x.a<y.a;
    }
    void doing1(int x,ll y) {
    	t[x].da=max(t[x].da,y);
    	ll u=y-t[x].biao;
    	if(t[x].biao2)t[x].biao1=max(t[x].biao1,u);
    	else t[x].biao2=1,t[x].biao1=u;
    }
    void doing2(int x,ll y) {
    	t[x].da+=y;
    	t[x].biao+=y;
    }
    void doing(int x) {
    	if(t[x].biao2!=0) {
    		doing1(x*2,t[x].biao1);
    		doing1(x*2+1,t[x].biao1);
    		t[x].biao1=t[x].biao2=0;
    	}
    	if(t[x].biao!=0) {
    		doing2(x*2,t[x].biao);
    		doing2(x*2+1,t[x].biao);
    		t[x].biao=0;
    	}
    }
    void change(int x,int l,int r,int y,int z,ll o) {
    	if (y>z) return;
    	if (l==y&&r==z) {
    		doing2(x,o);
    		return;
    	}
    	int mid=(l+r)/2;
    	doing(x);
    	if (z<=mid) change(x*2,l,mid,y,z,o);
    	else if (y>mid) change(x*2+1,mid+1,r,y,z,o);
    	else change(x*2,l,mid,y,mid,o),change(x*2+1,mid+1,r,mid+1,z,o);
    	t[x].da=max(t[x*2].da,t[x*2+1].da);
    }
    void change1(int x,int l,int r,int y,int z,ll o) {
    	if (y>z) return;
    	if (l==y&&r==z) {
    		doing1(x,o);
    		return;
    	}
    	int mid=(l+r)/2;
    	doing(x);
    	if (z<=mid) change1(x*2,l,mid,y,z,o);
    	else if (y>mid) change1(x*2+1,mid+1,r,y,z,o);
    	else change1(x*2,l,mid,y,mid,o),change1(x*2+1,mid+1,r,mid+1,z,o);
    	t[x].da=max(t[x*2].da,t[x*2+1].da);
    }
    ll find(int x,int l,int r,int y) {
    	if (l==r) return t[x].da;
    	int mid=(l+r)/2;
    	doing(x);
    	if (y<=mid)return find(x*2,l,mid,y);
    	else return find(x*2+1,mid+1,r,y);
    }
    int main() {
    	freopen("Fgarden.in","r",stdin);
    	freopen("Fgarden.out","w",stdout);
    	scanf("%d",&n);
    	fo(i,1,n) {
    		scanf("%lld%lld%lld",&e[i].a,&b[i],&c[i]);
    		e[i].d=i;
    	}
    	sort(e+1,e+n+1,cmp);
    	tot=1;
    	a[e[1].d]=tot;
    	fo(i,2,n) {
    		if(e[i-1].a!=e[i].a)a[e[i].d]=++tot;
    		else a[e[i].d]=tot;
    	}
     
    	fo(i,1,n) {
    		f[i]=b[i]+find(1,1,tot,a[i]);
    		change(1,1,tot,1,a[i]-1,-c[i]);
    		change1(1,1,tot,a[i],tot,f[i]);
    	}
    	memset(t,0,sizeof(t));
    	fod(i,n,1) {
    		g[i]=b[i]+find(1,1,tot,a[i]);
    		change(1,1,tot,1,a[i]-1,-c[i]);
    		change1(1,1,tot,a[i],tot,g[i]);
    	}
    	fo(i,1,n) {
    		ans=max(ans,f[i]+g[i]-b[i]);
    	}
    	printf("%lld",ans);
    }