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<algorithm>
#include<string>
#include<cmath>
#define int long long
#define mod 1000000007
using namespace std;
int d, n, t[250], a[250], b[250], c[250], dp[250][250], ans;
signed main() {
	cin >> d >> n;
	for (int i = 1; i <= d; i++) cin >> t[i];
	for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
	for (int i = 1; i <= n; i++)if (t[1] < a[i] || b[i] < t[1])dp[1][i] = -100000000;
	for (int i = 2; i <= d; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = -100000000;
			if (a[j] <= t[i] && t[i] <= b[j])
				for (int k = 1; k <= n; k++) {
					dp[i][j] = max(dp[i][j], dp[i - 1][k] + abs(c[k] - c[j]));
				}
			if (i == d)ans = max(ans, dp[i][j]);
		}
	}
	cout << ans << endl;
}

C++: #include<cstdio>
#include <iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<numeric>

#define MOD 1000000007

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

struct data {
	int mi_t;
	int mx_t;
	int c;
};
int d[210];

int main()
{
	int D, N;
	struct data Data[210];
	cin >> D >> N;

	for (int i = 0; i < D; i++) 
		cin >> d[i];

	for (int i = 0; i < N; i++) 
		cin >> Data[i].mi_t >> Data[i].mx_t >> Data[i].c;

	int ans = 0;
	for(int k=0; k<2; k++){
		int total = 0;
		int now_c=0, next_c=0;
		for (int i = 0; i < D; i++) {
			int t = d[i];
			int high = -1;
			int low = 100000000;
			for (int j = 0; j < N; j++) {
				if (i % 2 == k) {
					if (t >= Data[j].mi_t && Data[j].mx_t >= t) {
						high = max(high, Data[j].c);
						next_c = high;
					}
				}
				else {
					if (t >= Data[j].mi_t && Data[j].mx_t >= t) {
						low = min(low, Data[j].c);
						next_c = low;
					}
				}
			}
			if(i != 0)
			total += abs(now_c - next_c);
			swap(now_c, next_c);
		}
		ans = max(ans,total);
	}
	cout << ans << endl;
	return 0;
}

C++: #include <iostream>
#include <limits>
#include <cstring>
#include <cmath>

constexpr int MAX = 200;
constexpr int MAX_C = 100;

int D, N, T[MAX], A[MAX], B[MAX], C[MAX];
int memo[MAX_C + 1][MAX + 1];

int solve(int tmp, int n = 1);

int main(){
	std::ios::sync_with_stdio(false);
	
	memset(memo, -1, sizeof(memo));

	std::cin >> D >> N;

	for(int i = 0; i < D; ++i){
		std::cin >> T[i];
	}

	for(int i = 0; i < N; ++i){
		std::cin >> A[i] >> B[i] >> C[i];
	}

	int ans = 0;
	for(int i = 0; i < N; ++i){
		if(A[i] <= T[0] && T[0] <= B[i]){
			ans = std::max(ans, solve(C[i]));
		}
	}

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

int solve(int tmp, int n){
	if(n == D){
		return 0;
	}
	if(memo[tmp][n] != -1){
		return memo[tmp][n];
	}

	int res = 0;
	for(int i = 0; i < N; ++i){
		if(A[i] <= T[n] && T[n] <= B[i]){
			res = std::max(res, solve(C[i], n + 1) + abs(tmp - C[i]));
		}
	}
	//std::cout << "memo[" << tmp << "][" << n << "] = " << res << std::endl;
	return memo[tmp][n] = res;
}

C++: #include <iostream>
using namespace std;

int myabs(int x){
	if(x>0){
		return x;
	}
	else{
		return -x;
	}
}

int main(){
	int D,N;
	cin>>N>>D;
	int Dbox[200],Ubox[200],Sbox[200],Hbox[200];
	for(int i=0;i<N;i++){
		cin>>Dbox[i];
	}
	for(int i=0;i<D;i++){
		cin>>Sbox[i]>>Ubox[i]>>Hbox[i];
	}

	int Fuku[200][200];
	for(int i=0;i<N;i++){
		for(int j=0;j<D;j++){
			Fuku[i][j]=-1;
		}
	}
	int cnt,kaz;
	//0つめ
	for(int cfuku=0;cfuku<D;cfuku++){
		if(Dbox[0]<=Ubox[cfuku]&&Dbox[0]>=Sbox[cfuku]){
			Fuku[0][cfuku]=0;
		}
	}
	//１から
	for(int day=1;day<N;day++){
		for(int cfuku=0;cfuku<D;cfuku++){
			if(Dbox[day]<=Ubox[cfuku]&&Dbox[day]>=Sbox[cfuku]){
				cnt=0;
				for(int men=0;men<D;men++){
					if(Fuku[day-1][men]!=-1){
						if(cnt<myabs(Hbox[men]-Hbox[cfuku])){
							cnt=myabs(Hbox[men]-Hbox[cfuku]);
							kaz=men;
						}
					}
				}
				Fuku[day][cfuku]=cnt+Fuku[day-1][kaz];
			}
		}
	}
	cnt=0;
	for(int cfuku=0;cfuku<D;cfuku++){
		if(cnt<Fuku[N-1][cfuku]) cnt=Fuku[N-1][cfuku];
	}
	cout<<cnt<<endl;
	return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <sstream>
#include <cmath>

#define INT32_MAX 2147483647

using namespace std;

struct cloth {
    int min,max,c;

    bool operator<(const cloth& right) const {
        return c < right.c;
    }
};


int t[201];
cloth clothes[201];

inline bool isrange(int temp, cloth *c) {
    return (c->min <= temp) && (temp <= c->max);
}

int main() {
    int d,n;
    cin >> d >> n;
    for (int i = 0; i < d; ++i) {
        cin >> t[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> clothes[i].min >> clothes[i].max >> clothes[i].c;
    }
    sort(clothes, clothes + n);

    int result = 0;
    int prec;
    for (int j = 0; j < n; ++j) {
        if (!isrange(t[0], &clothes[j])) continue;

        prec = clothes[j].c;
        break;
    }

    for (int i = 1; i < d; ++i) {
        int todaytemp;
        for (int j = 0; j < n; ++j) {
            if (!isrange(t[i], &clothes[j])) continue;

            todaytemp = abs(prec - clothes[j].c);
            prec = clothes[j].c;
            break;
        }
        for (int j = n - 1; 0 <= j; --j) {
            if (!isrange(t[i], &clothes[j])) continue;

            int temp = abs(prec - clothes[j].c);
            if (temp < todaytemp) {
                result += todaytemp;
            } else {
                result += temp;
                prec = clothes[j].c;
            }
            break;
        }
    }

    cout << result << endl;

    return 0;
}

C++: #include<iostream>
#include<cstdlib>
using namespace std;

int t[65];
int d;
int n;
int garment[205][3];
int dp[205][65];
int ans;

int dfs(int, int);

int main()
{
  for(int i = 0; i < 205; i++)
  {
    for(int j = 0; j < 65; j++)
      dp[i][j] = -1;
  }

  cin >> d >> n;
  for(int i = 0; i < d; i++)
    cin >> t[i];
  for(int i = 0; i < n; i++)
    cin >> garment[i][1] >> garment[i][2] >> garment[i][0];

  for(int i = 0; i < n; i++)
  {
    if(t[0] >= garment[i][1] && t[0] <= garment[i][2])
    {
      ans = max(dfs(i, 1), ans);
    }
  }
  cout << ans << endl;
}

int dfs(int last, int day)
{
  //cout << " -- day" << day + 1 << " t" << t[day] << endl; 
  if(dp[last][day] != -1)
  {
    //cout << "dp" << endl;
    return dp[last][day];
  }  
  if(day == d)
  {
    //cout << "return " << day + 1 << endl;
    return 0;
  }

  int r = 0;
  for(int i = 0; i < n; i++)
  {
    //cout << garment[i][1] << " - " << garment[i][2] << ": " << garment[i][0]; 
    if(t[day] >= garment[i][1] && t[day] <= garment[i][2])
    {  
      //cout << "OK\n";
      r = max(dfs(i, day + 1) + abs(garment[i][0] - garment[last][0]), r);
      //cout << "----" << endl;
    }
    //else
      //cout << "NG\n";
  }
  dp[last][day] = r;
  return r;
}