Problem: Example

Input

2 10
10 200 1
10 100 100


Output

200

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> pos;

template <typename T, const T id>
class convex_hull_trick {
	struct line {
		T a, b;
		line(T a_ = 0, T b_ = 0) : a(a_), b(b_) {}
		T get(T x) { return a * x + b; }
	};
	struct node {
		line l;
		node *lch, *rch;
		node(line l_) : l(l_), lch(nullptr), rch(nullptr) {}
	};
	const int n;
	node *root;
	node* modify(node *p, int lb, int ub, line& l) {
		if (!p) return new node(l);
		if (p->l.get(pos[lb]) >= l.get(pos[lb]) && p->l.get(pos[ub]) >= l.get(pos[ub])) return p;
		if (p->l.get(pos[lb]) <= l.get(pos[lb]) && p->l.get(pos[ub]) <= l.get(pos[ub])) {
			p->l = l;
			return p;
		}
		int c = (lb + ub) >> 1;
		if (p->l.get(pos[c]) < l.get(pos[c])) swap(p->l, l);
		if (p->l.get(pos[lb]) <= l.get(pos[lb]))
			p->lch = modify(p->lch, lb, c, l);
		else
			p->rch = modify(p->rch, c + 1, ub, l);
		return p;
	}
	T sub(node *p, int lb, int ub, int t) const {
		if (!p) return id;
		if (ub - lb == 0) return p->l.get(pos[t]);
		int c = (lb + ub) >> 1;
		if (t <= c) return max(p->l.get(pos[t]), sub(p->lch, lb, c, t));
		return max(p->l.get(pos[t]), sub(p->rch, c + 1, ub, t));
	}
public:
	convex_hull_trick(int n_) : n(n_), root(nullptr) {}
	void insert(T a, T b) {
		line l(a, b);
		root = modify(root, 0, n - 1, l);
	}
	T get(T x) const {
		int t = lower_bound(pos.begin(), pos.end(), x) - pos.begin();
		assert(t < n && pos[t] == x);
		return sub(root, 0, n - 1, t);
	}
};

using CHT = convex_hull_trick<ll, LLONG_MIN>;

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int N, T;
	cin >> N >> T;
	vector<tuple<ll, ll, ll>> ftp(N);
	for (int i = 0; i < N; i++) {
		int t, p, f;
		cin >> t >> p >> f;
		ftp[i] = make_tuple(f, t, p);
	}
	sort(ftp.begin(), ftp.end());
	vector<ll> t(N), p(N), f(N);
	for (int i = 0; i < N; i++) {
		tie(f[i], t[i], p[i]) = ftp[i];
	}
	pos = f;
	sort(pos.begin(), pos.end());
	pos.erase(unique(pos.begin(), pos.end()), pos.end());
	vector<CHT> cht(T + 1, CHT(pos.size()));
	cht[0].insert(0, 0);
	ll res = 0;
	for (int i = 0; i < N; i++) {
		for (int j = T - t[i]; j > 0; j--) {
			if (cht[j].get(pos[0]) == LLONG_MIN) continue;
			ll val = p[i] + cht[j].get(f[i]) - f[i] * f[i];
			cht[j + t[i]].insert(2 * f[i], val - f[i] * f[i]);
			res = max(res, val);
		}
		cht[t[i]].insert(2 * f[i], p[i] - f[i] * f[i]);
		res = max(res, p[i]);
	}
	cout << res << endl;
	return 0;
}