Problem: Example

Input

2 10
10 200 1
10 100 100


Output

200

Solution (in CPP):

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

typedef long long ll;
#define INF (1LL<<60)

struct data{
  ll t,p,f;
  bool operator < (const data &p)const{
    return f<p.f;
  }
};

int N,T;
data a[MAX_N];

ll dp[MAX_T][MAX_N];
ll dm[MAX_T][MAX_N];

ll calc(int x,int y){
  if(y==0)return 0;
  return (a[x].f-a[y].f)*(a[x].f-a[y].f);
}

int main(){
  for(int i=0;i<MAX_T;i++){
    for(int j=0;j<MAX_N;j++){
      dp[i][j]=(j==0?0:-INF);
      dm[i][j]=(i==0||j==0?0:-INF);
    }
  }
  
  cin>>N>>T;
  a[0]=(data){0,0,0};
  
  for(int i=1;i<=N;i++){
    cin>>a[i].t>>a[i].p>>a[i].f;
  }
  sort(a+1,a+N+1);

  ll ans=0;
  
  for(int i=1;i<=T;i++){

    deque<int> deq;
    deq.push_back(0);
    
    for(int j=1;j<=N;j++){
      dp[i][j]=max(dp[i][j],dp[i-1][j]);
      if(i-a[j].t>=0){
        dp[i][j]=max(dp[i][j],dm[i-a[j].t][j]+a[j].p);
      }
      ans=max(ans,dp[i][j]);


      
      while(deq.size()>=2){
        int a=deq.front();deq.pop_front();
        int b=deq.front();
        if( dp[i][a]-calc(j,a) > dp[i][b]-calc(j,b) ){
          deq.push_front(a);
          break;
        }
      }
      
      int key=deq.front();
      dm[i][j]=dp[i][key]-calc(j,key);

      while(!deq.empty()){
        int a=deq.back();deq.pop_back();
        if( dp[i][a]-calc(j,a) > dp[i][j] ){
          deq.push_back(a);
          break;
        }
      }
      deq.push_back(j);
    }
  }

  cout<<ans<<endl;
  
  return 0;
}