Problem: Example

Input

2 10
10 200 1
10 100 100


Output

200

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using namespace std;
using ll=long long;

ll t[4010],p[4010],f[4010];
ll dp[4010][4010],ca[4010][4010],cb[4010][4010];

int deq[4010][4010],head[4010],tail[4010]; 

inline ll sq(ll n){return n*n;}

inline bool check(int base,int i,int j,int k){return (cb[base][j]-cb[base][i])*(ca[base][k]-ca[base][j])<=(cb[base][k]-cb[base][j])*(ca[base][j]-ca[base][i]);}
inline ll func(int base,int idx,ll x){return 1LL*ca[base][idx]*x+cb[base][idx];}

int main(void){
	ll N,T;
	cin >> N >> T;

	vector<tuple<ll,ll,ll>> ary(N);
	rep(i,N){
		ll tt,pp,ff;
		cin >> tt >> pp >> ff;
		ary[i]=make_tuple(ff,tt,pp);
	}

	sort(_all(ary));
	rep(i,N) tie(f[i],t[i],p[i])=ary[i];


	rep(i,1,N+1)rrep(j,T+1,t[i-1]){
		bool ok=true;
		if(j==t[i-1]){
			chmax(dp[i][j],p[i-1]);
		}else if(j>t[i-1]){
			const int base=j-t[i-1];
			if(tail[base]-head[base]==0) ok=false;
			while(tail[base]-head[base]>=2 && func(base,deq[base][head[base]],f[i-1])<= func(base,deq[base][head[base]+1],f[i-1]) ) head[base]++;
			if(ok) chmax(dp[i][j],p[i-1]-sq(f[i-1])+func(base,deq[base][head[base]],f[i-1]));
			//cout << i << " " << j << " " << dp[i][j] << endl;
		}

		if(ok==false) continue;
		const int base=j;
		ca[base][i-1]=2LL*f[i-1],cb[base][i-1]=-sq(f[i-1])+dp[i][j];
		while(tail[base]-head[base]>=2 && check(base,deq[base][tail[base]-2],deq[base][tail[base]-1],i-1)) tail[base]--;
		deq[base][tail[base]++]=i-1;
	}

	ll ans=0LL;
	rep(i,N+1) rep(j,T+1) chmax(ans,dp[i][j]);
	cout << ans << endl;

	return 0;
}