I know how to solve it,but I just can't code it correctly...
I use splay to implement it,and the third test case of the sample's answer is wrong.
code:
#include <bits/stdc++.h>
#define il inline
using namespace std;
typedef long long ll;
il void cmin(ll &x,ll y){x=x<y?x:y;}
il int ab(int x){return x>0?x:-x;}
const int N=2e5+5,inf=1e9;
int T,n;ll f[N],g[N],sum;
struct node{
int s[2],fa,v,siz;ll w;
il node(){s[0]=s[1]=fa=v=siz=0,w=0;}
}t[N];ll tag[N];int tot,rt;
il void PRINT(){
puts("----------------- TREE STRUCTURE");
for(int i=0;i<=tot;++i) printf("%d %d %d %d\n",i,t[i].fa,t[i].s[0],t[i].s[1]);puts("");
}
il int get(int x){return t[t[x].fa].s[1]==x;}
il void INIT(int x){t[x].s[0]=t[x].s[1]=t[x].fa=t[x].v=t[x].siz=0,t[x].w=tag[x]=0;}
il int NEW(int fa,int v,ll w){int x=++tot;t[x].s[0]=t[x].s[1]=0,t[x].fa=fa,t[x].v=v,t[x].siz=1,t[x].w=w;return x;}
il void pushup(int x){t[x].siz=t[t[x].s[0]].siz+t[t[x].s[1]].siz+1;}
il void rot(int x){
if(!x) return ;
//printf("- 1 %d %d\n",x,t[0].siz);
int y=t[x].fa,z=t[y].fa,c=get(x),u=t[x].s[!c];
t[z].s[get(y)]=x,t[x].fa=z;
t[y].s[c]=u,t[u].fa=y;
t[x].s[!c]=y,t[y].fa=x;
/*if(!y || !x){
printf("--------------- *** %d %d %d\n",x,y,z);
exit(0);
}*/
//printf("- 2 %d %d\n",x,t[0].siz);
pushup(y),pushup(x);
}
il void maketag(int x,ll w){if(x) t[x].w+=w,tag[x]+=w;}
il void pushdown(int x){
if(!x) return ;
if(tag[x]) maketag(t[x].s[0],tag[x]),maketag(t[x].s[1],tag[x]),tag[x]=0;
}
il void build(int &x,int l,int r){
if(l>r) return ;
if(!x) x=++tot;
if(l==r){t[x].v=(l?inf:-inf),t[x].siz=1;return ;}
int mid=(l+r)>>1;t[x].v=mid,t[x].w=f[1],t[x].siz=1;
if(l<=mid-1) build(t[x].s[0],l,mid-1),t[t[x].s[0]].fa=x;
if(mid+1<=r) build(t[x].s[1],mid+1,r),t[t[x].s[1]].fa=x;
pushup(x);
}
il void splay(int x,int to){
int y,z;
while(t[x].fa!=to){
if(!x) break;
y=t[x].fa,z=t[y].fa,pushdown(z),pushdown(y),pushdown(x);
if(z!=to){
if(get(x)==get(y)) rot(y);else rot(x);
}rot(x);
}if(!to) rt=x;
}
il int get_v(int k){
int x=rt,y,z;++k;
while(k){
y=t[x].s[0];pushdown(x);
if(k<=t[y].siz) x=y;
else if(k>t[y].siz+1) k-=t[y].siz+1,x=t[x].s[1];
else return x;
}return 0;
}
il void insert(int p,ll w){
/*if(t[0].siz){
puts("befffff ********************************************");
printf("%d %lld\n",p,w);
PRINT();
exit(0);
}*/
int x=get_v(p),y=get_v(p+1),z=-1;
/*if(t[0].siz || !x || !y || !z){
puts("bef ********************************************");
printf("%d %d %d %d %lld\n",x,y,z,p,w);
PRINT();
exit(0);
}*/
splay(x,0),splay(y,x);
/*if(t[0].siz || !x || !y || !z){
puts("********************************************");
printf("%d %d %d %d %lld\n",x,y,z,p,w);
PRINT();
exit(0);
}*/
z=NEW(y,p+1,w),t[y].s[0]=z;
/*if(t[0].siz || !x || !y || !z){
puts("********************************************");
printf("%d %d %d %d %lld\n",x,y,z,p,w);
PRINT();
exit(0);
}*/
pushup(y),pushup(x);
}
il void update(int l,int r,ll w){
int x=get_v(l-1),y=get_v(r+1),z;splay(x,0),splay(y,x),z=t[y].s[0];
/*if(t[0].siz || !x || !y || !z){
puts("********************************************");
printf("%d %d %d %d %d %lld\n",x,y,z,l,r,w);
PRINT();
exit(0);
}*/
pushdown(x),pushdown(y);
maketag(z,w);
pushup(y),pushup(x);
}
il ll query(int p){
int x=get_v(p-1),y=get_v(p+1),z;splay(x,0),splay(y,x),z=t[y].s[0];
/*if(t[0].siz || !x || !y || !z){
puts("********************************************");
printf("%d %d %d %d\n",x,y,z,p);
PRINT();
exit(0);
}*/
pushdown(x),pushdown(y);
return t[z].w;
}
int getnxt(int x,int cur,ll K,ll B){
//if(t[0].siz) puts("***");
if(!x) return 0;
int y=t[x].s[0],z=t[x].s[1],p;ll u,v,w;
if(ab(t[x].v)==inf) return y?getnxt(y,cur,K,B):getnxt(z,cur+t[y].siz+1,K,B);
pushdown(x);
u=t[x].w,v=K*(1ll*cur+t[y].siz)+B;
if(u<=v){
p=(z?getnxt(z,cur+t[y].siz+1,K,B):0);
return p?p:cur+t[y].siz;
}
else return getnxt(y,cur,K,B);
}
struct P{
ll a,b,k;
il P(){a=b=k=0;}
}a[N];
il bool cmp(P x,P y){return x.k>y.k;}
il void init(){
for(int i=0;i<=tot;++i) INIT(i);
rt=tot=0;
}
int x,y,z;ll u,v,w;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);sum=0,init();
for(int i=1;i<=n;++i) scanf("%lld%lld%lld",&a[i].k,&a[i].b,&a[i].a),sum+=a[i].a;
sort(a+1,a+1+n,cmp);
for(int i=0;i<=n+1;++i) f[i]=0;
f[1]=a[1].k-(a[1].b-a[1].a);
build(rt,0,2);//printf("%d\n",get_v(2)),PRINT();
for(int i=1;i<=n;++i){
x=0,w=a[i].b-a[i].a;
//while(x<i-1 && f[x+1]<=a[i].k*(x+1ll)-w) ++x;
//printf("*********** %d %d\n",i,t[0].siz);
x=getnxt(rt,0,a[i].k,-w);
//printf("------------*********** %d %d %d\n",i,x,t[0].siz);
insert(x,a[i].k*(x+1ll)-w);
//printf("-------------------------*********** %d %d\n",i,t[0].siz);
if(x+2<=i) update(x+2,i,a[i].k);
// printf("*********** %d %d\n",i,t[0].siz);
// for(int j=i;j>x+1;--j) f[j]=f[j-1]+a[i].k;
//f[x+1]=a[i].k*(x+1ll)-w;
}
w=0,v=0;for(int i=1;i<=n;++i) cmin(w,v+=query(i));
printf("%lld\n",sum-w);
init();
}
return 0;
}
/*
1
4
10000 1000000000 2006
10000 1000000000 9999
2 999991010 1010
1000000000 1000000000 999999999
*/
