Go: ///
// File:  0579.go
// Author: ymiyamoto
//
// Created on Mon Mar 19 18:46:50 2018
//
package main

import (
	"fmt"
)

var D, N int

type cloth struct {
	A, B, C int
}

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func main() {
	fmt.Scan(&D, &N)
	thermals := make([]int, D+1)

	for i := 1; i <= D; i++ {
		fmt.Scan(&thermals[i])
	}

	clothes := make([]cloth, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&clothes[i].A, &clothes[i].B, &clothes[i].C)
	}

	dp := make([][]int, D+1)
	for i := range dp {
		dp[i] = make([]int, N)
	}

	for i := 1; i < D; i++ {
		for j := 0; j < N; j++ {
			for k := 0; k < N; k++ {
				t1 := thermals[i]
				t2 := thermals[i+1]
				if clothes[j].A <= t2 && t2 <= clothes[j].B && clothes[k].A <= t1 && t1 <= clothes[k].B {
					dp[i+1][j] = max(dp[i+1][j], dp[i][k]+abs(clothes[j].C-clothes[k].C))
				}
			}
		}
	}

	val := 0
	for _, v := range dp[D] {
		val = max(val, v)
	}

	fmt.Println(val)
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <complex>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) begin(a),end(a)
#define MS(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef complex<double> Point;
typedef long long ll;
const int INF = 114514810;
const int MOD = 1000000007;
const double EPS = 1e-8;
const double PI = acos(-1.0);
struct edge
{
  int from, to, cost;
  bool operator < (const edge& e) const { return cost < e.cost; }
  bool operator >(const edge& e) const { return cost > e.cost; }
};
///*************************************************************************************///
///*************************************************************************************///
///*************************************************************************************///

struct huku
{
	int x,y,z;
};
int D,N;
int dp[205][205];
int d[205];
huku h[205];

int solve(int i, int j)
{
	if(dp[i][j] >=0) return dp[i][j];
	if(i==D) return 0;
	int res = 0;
	if(i==0)
	{
		REP(k,N)
		{	
			if(d[i]>=h[k].x&&d[i]<=h[k].y) res = max(res,solve(i+1,k));
		}
	}
	else
	{
		REP(k,N)
		{
			if(d[i]>=h[k].x&&d[i]<=h[k].y) res = max(res,solve(i+1,k)+abs(h[k].z-h[j].z));
		}
	}
	return dp[i][j] = res;
}

int main()
{
	MS(dp,-1);
	cin>>D>>N;
	REP(i,D) cin>>d[i];
	REP(i,N)
	{
		int a,b,c;cin>>a>>b>>c;
		huku t = {a,b,c};
		h[i] = t;
	}
	cout<<solve(0,0)<<endl;

	return 0;
}

C++: #include <bits/stdc++.h>

using namespace std;

int D,N;
int temp[201];
int cloth[61][3];
int a[201][61][61];


int dp(int d,int yk,int k){
	if(d > 0){
		if(!(cloth[k][0] <= temp[d] && cloth[k][1] >= temp[d]))return 0;
	}

	if(a[d][yk][k] >= 0) return a[d][yk][k];

	if(d == D){
		return a[d][yk][k] = fabs(cloth[yk][2] - cloth[k][2]) ;
	}

	int eva = 0;
	int sum = 0;
	for(int i = 1; i <= N ;i++){
		if(d < 2){
			sum = dp(d+1, k, i);
			eva = max(eva,sum);
		}else{
			sum = dp(d +1, k, i) + fabs(cloth[yk][2] - cloth[k][2]);
			eva = max(eva,sum);
		}
	}

	return a[d][yk][k] = eva;


	// long long int eva = 0;
	// long long int sum = 0;
	// if(d >= 2){

	// 	eva = fabs(yeva - cloth[k][2]);
	// }

	// if(d == D){
	// 	// cout<<d<<" "<<k<<" "<<eva<<endl;
	// 	return a[d][k] = eva;
	// }


	// for(int i = 1;i <= N;i++){
	// 	if(d == 0){
	// 		eva = max(eva, dp(d+1, i, 0));
	// 	}else if( d == 1){
	// 		// cout<<sum<< " "<<eva<<endl;
	// 		// cout<<eva<<" "<<dp(d+1,i,cloth[k][2])<<endl;
	// 		eva = max(eva,dp(d+1, i, cloth[k][2]));
	// 	}else{
	// 		sum = dp(d+1,i,cloth[k][2]) + eva;
	// 		cout<<d<<" "<<dp(d+1,i,cloth[k][2])<<" "<<eva <<" "<<sum<<endl;
	// 		// cout<<eva<<" "<<dp(d+1,i,cloth[k][2])<<endl;
	// 		eva = max(eva,sum);
	// 	}
	// }
	// // cout << d <<" " <<k<<" " << eva <<endl; 
	// return a[d][k] = eva;
}


int main(){
	fill_n(temp,201,-1);
	fill_n(*cloth,61*3,-1);
	fill_n(**a,201*61*61,-1);
	cin >> D >> N;
	for(int i = 1;i <= D;i++){
		cin >>temp[i];
	}
	for(int i = 1;i <= N;i++){
		for(int j = 0;j < 3;j++){
			cin >> cloth[i][j];
		}
	}
	cout << dp(0,0,0) << endl;
}

C++: #include <bits/stdc++.h>
using namespace std;
 
struct uyu{int a, b, c;};
 
int d, n;
int t[202];
vector<uyu> po;
 
int dp[256][256];
 
int dfs(int i=0, int pre=0)
{
   
  if (i == d) return 0;
  int &ret = dp[i][pre];
  if (ret != -1) return ret;
  if (i == 0){
    for (int j = 0; j < n; j++){
      if (t[i] < po[j].a || po[j].b < t[i]) continue;
      ret = max(ret, dfs(i + 1, j));
    }
    return ret;
  }
 
  for (int j = 0; j < n; j++){
    if (t[i] < po[j].a || po[j].b < t[i]) continue;
    ret = max(ret, dfs(i + 1, j) + abs(po[j].c - po[pre].c));
  }
 
  return ret;
}
 
int main()
{
  memset(dp, -1, sizeof(dp));
  cin >> d >> n;
  for (int i = 0; i < d; i++){
    cin >> t[i];
  }
 
  for (int i = 0; i < n; i++){
    uyu s;
    cin >> s.a >> s.b >> s.c;
    po.push_back(s);
  }
 
  cout << dfs() << endl;
}

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

#define llong long long 
typedef struct data{
	int low;
	int high;
	int eva;
}data;
int D, N;
int temp[201];
data kind[200];
int score[201][200];

int solve(int d, int k, int e){
	//cout << d << " " << k << " " << e << "   " << score[d][k] << endl;
	score[d][k] = e;
	// if(!(d < 1) && score[d][k] > e) return score[d][k];
	if(d == D) return e;
	int ret = 0;
	for(int i = 0; i < N; i++){
		data use = kind[i];
		if(use.low > temp[d + 1] || use.high < temp[d + 1]) continue;
		if(d > 0) ret = max(ret, solve(d + 1, i, e + fabs(kind[k].eva - kind[i].eva)) );
		else ret = max(ret, solve(d + 1, i, 0));
	}

	return ret;
}

int main(){
	fill_n(temp, 201, -1);
	fill_n(*score, 201 * 200, 0);
	cin >> D >> N;
	for(int i = 1; i <= D; i++){
		cin >> temp[i];
	}
	for(int i = 0; i < N; i++){
		cin >> kind[i].low >> kind[i].high >> kind[i].eva;
	}

	cout << solve(0, 0, -1) << endl;
	return 0;
}

C++: #include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

struct Info{
	Info(){
		min = max = value = 0;
	}
	int min,max,value;
};

int main(){

	int D,N;
	scanf("%d %d",&D,&N);

	int temperature[D];

	for(int i = 0; i < D; i++){
		scanf("%d",&temperature[i]);
	}

	Info info[N];
	int dp[D+1][N];
	for(int i = 0; i < D+1; i++){
		for(int k = 0; k < N; k++)dp[i][k] = -1;
	}

	for(int i = 0; i < N; i++){
		scanf("%d %d %d",&info[i].min,&info[i].max,&info[i].value);
	}

	int maximum = 0;

	for(int i = 0; i < N; i++){
		if(info[i].min <= temperature[1] && info[i].max >= temperature[1]){
			for(int k = 0; k < N; k++){
				if(info[k].min <= temperature[0] && info[k].max >= temperature[0]){
					dp[2][i] = max(dp[2][i],abs(info[i].value-info[k].value));
					maximum = max(maximum,dp[2][i]);
				}
			}
		}
	}



	for(int day = 3; day <= D; day++){
		for(int i = 0; i < N; i++){
			if(info[i].min <= temperature[day-1] && info[i].max >= temperature[day-1]){
				for(int k = 0; k < N; k++){
					if(dp[day-1][k] != -1){
						dp[day][i] = max(dp[day][i],dp[day-1][k] + abs(info[i].value-info[k].value));
						maximum = max(maximum,dp[day][i]);
					}
				}
			}
		}
	}

	printf("%d\n",maximum);

	return 0;
}