Language: C++

#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<__int128,__int128> P;

struct data{
	int t;
	ll p,f;
	data(){}
	data(int tt,ll pp,ll ff){
		t=tt;
		p=pp;
		f=ff;
	}

	bool operator<(const data &d)const{
		if(d==d.f)return p<d.p;
		return f<d.f;
	}
};

struct CHTrick{
	vector<P> lines;
	bool isMonoticX=false;
	CHTrick(bool flag=false){
		isMonoticX=flag;
	}

	bool check(P l1,P l2,P l3){
		if(l1<l3)swap(l1,l3);
		/*
		if(l3.second-l2.second>=0LL && l2.first-l1.first>=0LL)assert((l3.second-l2.second)*(l2.first-l1.first)>=0LL);
		if(l3.second-l2.second>=0LL && l2.first-l1.first<0LL)assert((l3.second-l2.second)*(l2.first-l1.first)<0LL);
		if(l3.second-l2.second<0LL && l2.first-l1.first>=0LL)assert((l3.second-l2.second)*(l2.first-l1.first)<0LL);
		if(l3.second-l2.second<0LL && l2.first-l1.first<0LL)assert((l3.second-l2.second)*(l2.first-l1.first)>=0LL);
		if(l2.second-l1.second>=0LL && l3.first-l2.first>=0LL)assert((l2.second-l1.second)*(l3.first-l2.first)>=0LL);
		if(l2.second-l1.second>=0LL && l3.first-l2.first<0LL)assert((l2.second-l1.second)*(l3.first-l2.first)<0LL);
		if(l2.second-l1.second<0LL && l3.first-l2.first>=0LL)assert((l2.second-l1.second)*(l3.first-l2.first)<0LL);
		if(l2.second-l1.second<0LL && l3.first-l2.first<0LL)assert((l2.second-l1.second)*(l3.first-l2.first)>=0LL);
		*/
		return (l3.second-l2.second)*(l2.first-l1.first)<=(l2.second-l1.second)*(l3.first-l2.first);
	}

	void add(ll a,ll b){
		P line(a,b);
		while(lines.size()>=2 && check(*(lines.end()-2),lines.back(),line)){
			lines.pop_back();
		}
		lines.push_back(line);
	}

	__int128 f(int i,ll x){
		return lines[i].first*x+lines[i].second;
	}
	__int128 f(P line,ll x){
		return line.first*x+line.second;
	}

	bool comp(ll lv,ll rv){
		return lv<=rv;
	}

	int head=0;
	ll get(ll x){
		if(isMonoticX){
			while(head>=lines.size())head--;
			while(lines.size()-head>=2 && comp(f(head,x),f(head+1,x)))head++;
			return f(head,x);
		}else{
			int low=-1,high=lines.size()-1;
			while(high-low>1){
				int mid=(high+low)/2;
				if(comp(f(mid,x),f(mid+1,x)))low=mid;
				else high=mid;
			}
			return f(high,x);
		}
	}
};

int n,T;
data d[4005];

CHTrick dp[4005];

int main(void){
	scanf("%d%d",&n,&T);
	for(int i=0;i<n;i++){
		scanf("%d%lld%lld",&d[i].t,&d[i].p,&d[i].f);
	}
	sort(d,d+n);
	dp[0].add(0,0);
	ll ans=0;
	for(int i=0;i<n;i++){
		for(int j=T-d[i].t;j>=0;j--){
			if(dp[j].lines.size()==0)continue;
			ll v=dp[j].get(d[i].f)+d[i].p-d[i].f*d[i].f;
			if(j==0){
				v+=d[i].f*d[i].f;
			}
			ans=max(v,ans);
			dp[j+d[i].t].add(2LL*d[i].f,v-d[i].f*d[i].f);
		}
	}
	printf("%lld\n",ans);
	return 0;
}


Compiler output:
a.cc: In member function 'bool data::operator<(const data&) const':
a.cc:18:21: error: no match for 'operator==' (operand types are 'const data' and 'const ll' {aka 'const long long int'})
   18 |                 if(d==d.f)return p<d.p;
      |                    ~^~~~~
      |                    |    |
      |                    |    const ll {aka const long long int}
      |                    const data
In file included from /usr/include/c++/14/regex:68,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:181,
                 from a.cc:1:
/usr/include/c++/14/bits/regex.h:1103:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator==(const sub_match<_BiIter>&, const sub_match<_BiIter>&)'
 1103 |     operator==(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1103:5: note:   template argument deduction/substitution failed:
a.cc:18:25: note:   'const data' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   18 |                 if(d==d.f)return p<d.p;
      |                         ^
/usr/include/c++/14/bits/regex.h:1199:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator==(__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const sub_match<_BiIter>&)'
 1199 |     operator==(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1199:5: note:   template argument deduction/substitution failed:
a.cc:18:25: note:   'const data' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
   18 |                 if(d==d.f)return p<d.p;
      |                         ^
/usr/include/c++/14/bits/regex.h:1274:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator==(const sub_match<_BiIter>&, __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
 1274 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1274:5: note:   template argument deduction/substitution failed:
a.cc:18:25: note:   'const data' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   18 |                 if(d==d.f)return p<d.p;
      |                         ^
/usr/include/c++/14/bits/regex.h:1366:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const typename std::iterator_traits<_Iter>::value_type*, const sub_match<_BiIter>&)'
 1366 |     operator==(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1366:5: note:   template argument deduction/substitution failed:
a.cc:18:25: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'const ll' {aka 'const long long int'}
   18 |                 if(d==d.f)return p<d.p;
      |                         ^
/usr/include/c++/14/bits/regex.h:1441:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
 1441 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1441:5: note:   template argument deduction/substitution failed:
a.cc:18:25: note:   'const data' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   18 |                 if(d==d.f)return p<d.p;
      |                         ^
/usr/include/c++/14/bits/regex.h:1534:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const typename std::iterator_traits<_Iter>::value_type&, const sub_match<_BiIter>&)'
 1534 |     operator==(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1534:5: note:   template argument deduction/substitution failed:
a.cc:18:25: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'const ll' {aka 'const long long int'}
   18 |                 if(d==d.f)return p<d.p;
      |                         ^
/usr/include/c++/14/bits/regex.h:1613:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
 1613 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1613:5: note:   template argument deduction/substitution failed:
a.cc:18:25: note:   'const data' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   18 |                 if(d==d.f)return p<d.p;
      |                         ^
/usr/include/c++/14/bits/regex.h:2186:5: note: candidate: 'template<class _Bi_iter, class _Alloc> bool std::__cxx11::operator==(const match_results<_BiIter, _Alloc>&, const match_results<_BiIter, _Alloc>&)'
 2186 |     operator==(const match_results<_Bi_iter, _Alloc>& __m1,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:2186:5: note:   template argument deduction/substitution failed:
a.cc:18:25: note:   'const data' is not derived from 'const std::__cxx11::match_results<_BiIter, _Alloc>'
   18 |                 if(d==d.f)return p<d.p;
      |                         ^
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51:
/usr/include/c++/14/bits/stl_pair.h:1033:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator==(const pair<_T1, _T2>&, const pair<_T1, _T2>&)'
 1033 |     operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1033:5: note:   template argument deduction/substitution failed:
a.cc:18:25: note:   'const data' is not derived from 'const std::pair<_T1, _T2>'
   18 |                 if(d==d.f)return p<d.p;
      |                         ^
In file included from /usr/include/c++/14/bits/stl_algobase.h:67:
/usr/include/c++/14/bits/stl_iterator.h:441:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator==(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  441 |     operator==(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:441:5: note:   template argument deduction/substitution failed:
a.cc:18:25: note:   'const data' is not derived from 'const std::reverse_iterator<_Iterator>'
   18 |                 if(d==d.f)return p<d.p;
      |                         ^
/usr/include/c++/14/bits/stl_iterator.h:486:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  486 |     operator==(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:486:5: note:   template argument deduction/substitution failed:
a.cc:18:25: note:   'const data' is not derived from 'const std::reverse_iterator<_Iterator>'
   18 |                 if(d==d.f)return p<d.p;
      |                         ^
/usr/include/c++/14/bits/stl_iterator.h:1667:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)'
 1667 |     operator==(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1667:5: note:   template argument deduction/substitution failed:
a.cc:18:25: note:   'const data' is not derived from 'const std::move_iterator<_IteratorL>'
   18 |                 if(d==d.f)return p<d.p;
      |                         ^
/usr/include/c++/14/bits/stl_iterator.h:1737:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator==(const move_iterator<_IteratorL>&, const move_iterator<_IteratorL>&)'
 1737 |     operator==(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1737:5: note:   template argument deduction/substitution failed:
a.cc:18:25: note:   'const data' is not derived from 'const std::move_iterator<_IteratorL>'
   18 |                 if(d==d.f)return p<d.p;
      |                         ^
In file included from /usr/include/c++/14/bits/char_traits.h:42,
                 from /usr/include/c++/14/string:42,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52:
/usr/include/c++/14/bits/postypes.h:192:5: note: candidate: 'template<class _StateT> bool std::operator==(const fpos<_StateT>&, const fpos<_StateT>&)'
  192 |     operator==(const fpos<_StateT>& __lhs, const fpos<_StateT>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/14/bits/postypes.h:192:5: note:   template argument deduction/substitution failed:
a.cc:18:25: note:   'const data' is not derived from 'const std::fpos<_StateT>'
   18 |                 if(d==d.f)return p<d.p;
      |                         ^
In file included from /usr/include/c++/14/string:43:
/usr/include/c++/14/bits/allocator.h:235:5: note: candidate: 'template<class _T1, class _T2> bool std::operator==(const allocator<_CharT>&, const allocator<_T2>&)'
  235 |     operator==(const allocator<_T1>&, const allocator<_T2>&)
      |     ^~~~~~~~
/usr/include/c++/14/bits/allocator.h:235:5: note:   template argument deduction/substitution failed:
a.cc:18:25: note:   'const data' is not derived from 'const std::allocator<_CharT>'
   18 |                 if(d==d.f)return p<d.p;
      |                         ^
In file included from /usr/include/c++/14/bits/basic_string.h:47,
                 from /usr/include/c++/14/string:54:
/usr/include/c++/14/string_view:629:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator==(basic_string_view<_CharT, _Traits>, __type_identity_t<basic_string_view<_CharT, _Traits> >)'
  629 |     operator==(basic_string_view<_CharT, _Traits> __x,
      |     ^~~~~~~~
/usr/include/c++/14/string_view:629:5: note:   template argument deduction/substitution failed:
a.cc:18:25: note:   'data' is not derived from 'std::basic_string_view<_CharT, _Traits