Problem: Example

Input

2 10
10 200 1
10 100 100


Output

200

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 4005


struct Info{

	bool operator<(const struct Info &arg) const{
		return diff_value < arg.diff_value;
	}
	ll weight,base_value,diff_value;
};

int N;
int minimum[NUM];
ll W;
ll dp[NUM][NUM]; //dp[何番目までの歌を見たか][時間の合計]
Info info[NUM];

int main(){

	scanf("%d %lld",&N,&W);

	info[0].base_value = 0;
	info[0].diff_value = 0;
	for(int i = 1; i <= N; i++){
		scanf("%lld %lld %lld",&info[i].weight,&info[i].base_value,&info[i].diff_value);
	}

	if(N == 1){
		printf("%lld\n",info[1].base_value);
		return 0;
	}

	sort(info,info+N+1);

	for(int i = 0; i <= N; i++){
		dp[i][0] = 0;
		for(int k = 1; k <= W; k++){
			dp[i][k] = -HUGE_NUM;
		}
	}

	dp[0][0] = 0;

	ll min_weight = BIG_NUM;
	ll ans = 0;

	//各歌が先頭になる値をまず計算
	for(int i = 1; i <= N; i++){
		dp[i][info[i].weight] = info[i].base_value;
		ans = max(ans,info[i].base_value);
		min_weight = min(min_weight,info[i].weight);
	}
	ll max_pre_value;
	int pre_deq_index;

	ll a,x,pre_x;

	for(int i = 0; i <= W; i++){
		minimum[i] = 0;
	}

	int debug = -1;
	ll tmp_weight;

	for(int song = 1; song <= N; song++){ //歌のループ
	//for(int song = 1; song <= 3; song++){

		a = info[song].diff_value;

		for(ll w = 1 ; w <= W; w++){ //重みのループ

			dp[song][w] = max(dp[song][w],dp[song][w-1]);
			if(w < info[song].weight)continue;

			max_pre_value = -HUGE_NUM;
			tmp_weight = w-info[song].weight;

			for(int i = minimum[tmp_weight]; i < song; i++){
				if(dp[i][tmp_weight] == -HUGE_NUM){
					continue;
				}
				x = info[i].diff_value;
				if(max_pre_value < dp[i][w-info[song].weight]+(2*a*x-x*x)){
					max_pre_value = dp[i][w-info[song].weight]+(2*a*x-x*x);
					pre_deq_index = i;
					pre_x = x;
				}
			}

			if(max_pre_value == -HUGE_NUM)continue;

			dp[song][w] = max(dp[song][w],dp[pre_deq_index][tmp_weight]+(2*a*pre_x-pre_x*pre_x)+info[song].base_value-a*a);
			ans = max(ans,dp[song][w]);

			//以後、最適になることのない値はDEQUEから論理削除する
			while(minimum[tmp_weight] < pre_deq_index){
				minimum[tmp_weight]++;
			}
			debug = pre_deq_index;
		}
	}

	printf("%lld\n",ans);

	return 0;
}