Problem: Example

Input

2 10
10 200 1
10 100 100


Output

200

Solution (in CPP):

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e9
#define mod 1000000007

struct song{
  ll t,p,f;
};

ll N,T;
vector<song> ss;
ll t[4001],p[4001],f[4001];
ll dp[4001][4001];
deque<P> deq[4001];

ll calc(P func,ll x){ return func.fi*x+func.se; }

bool check(P f1,P f2,P f3){
  ll a1=f1.fi, b1=f1.se;
  ll a2=f2.fi, b2=f2.se;
  ll a3=f3.fi, b3=f3.se;
  return (a2-a1)*(b3-b2)>=(b2-b1)*(a3-a2);
}

void add(ll k,ll A,ll B){
  ll sz=deq[k].size();
  while(deq[k].size()>1&&check(deq[k][sz-2],deq[k][sz-1],P(A,B))){
    deq[k].pop_back(); sz=deq[k].size();
  }
  deq[k].push_back(P(A,B));
}

ll query(ll k,ll x){
  if(deq[k].size()==0)return -INF;
  while(deq[k].size()>1&&calc(deq[k][0],x)<=calc(deq[k][1],x)){
    deq[k].pop_front(); 
  }
  return calc(deq[k][0],x);
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin>>N>>T;
  rep(i,N){
    ll tt,pp,ff;
    cin>>tt>>pp>>ff;
    ss.push_back((song){tt,pp,ff});
  }
  sort(all(ss),[](const song& a,const song& b){
    if(a.f==b.f) return a.p < b.p;
    else return a.f < b.f;
  });
  rep(i,N){
    t[i]=ss[i].t; p[i]=ss[i].p; f[i]=ss[i].f;
  }
  rep(i,4001)rep(j,4001)dp[i][j]=-INF;
  rep(i,N){
    dp[i][t[i]]=p[i];
  }

  ll res=0;
  rep(i,N){
    rep(j,T+1){
      ll l=j-t[i];
      if(l>0){
        maxch(dp[i][j],p[i]-f[i]*f[i]+query(l,f[i]));
      }
      maxch(res,dp[i][j]);
    }
    rep(j,T+1){
      if(dp[i][j]!=-INF)add(j,2LL*f[i],dp[i][j]-f[i]*f[i]);
    }
  }

  cout<<res<<endl;
  return 0;
}