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 <bits/stdc++.h>

#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());

typedef long long LL;
template<typename T> using V = std::vector<T>;
template<typename T> using VV = std::vector<std::vector<T>>;
template<typename T> using VVV = std::vector<std::vector<std::vector<T>>>;

template<class T> inline T ceil(T a, T b) { return (a + b - 1) / b; }
template<class T> inline void print(T x) { std::cout << x << std::endl; }
template<class T> inline void print_vec(const std::vector<T> &v) { for (int i = 0; i < v.size(); ++i) {  if (i != 0) {std::cout << " ";} std::cout << v[i];} std::cout << "\n"; }
template<class T> inline bool inside(T y, T x, T H, T W) {return 0 <= y and y < H and 0 <= x and x < W; }
template<class T> inline double euclidean_distance(T y1, T x1, T y2, T x2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }
template<class T> inline double manhattan_distance(T y1, T x1, T y2, T x2) { return abs(x1 - x2) + abs(y1 - y2); }

const int INF = 1L << 30;
const double EPS = 1e-9;
const std::string YES = "YES", Yes = "Yes", NO = "NO", No = "No";
const std::vector<int> dy4 = { 0, 1, 0, -1 }, dx4 = { 1, 0, -1, 0 };    // 4近傍（右, 下, 左, 上）
const std::vector<int> dy8 = { 0, -1, 0, 1, 1, -1, -1, 1 }, dx8 = { 1, 0, -1, 0, 1, 1, -1, -1 };

using namespace std;

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

    int D, N;
    cin >> D >> N;
    vector<int> T(D);
    FOR(i, 0, D) {
        cin >> T[i];
    }

    vector<tuple<int, int, int>> C;
    FOR(i, 0, N) {
        int a, b, c;
        cin >> a >> b >> c;
        C.emplace_back(make_tuple(a, b, c));
    }

    vector<vector<LL>> dp(D, vector<LL>(101, -1));
    FOE(t, C) {
        int a, b, c;
        tie(a, b, c) = t;
        if (a <= T[0] and T[0] <= b) {
            dp[0][c] = 0;
        }
    }


    FOR(i, 0, D - 1) {
        FOR(j, 0, dp[0].size()) {
            if (dp[i][j] == -1) {
                continue;
            }

            FOE(t, C) {
                int a, b, c;
                tie(a, b, c) = t;

                if (a <= T[i + 1] and T[i + 1] <= b) {
                    dp[i + 1][c] = max(dp[i + 1][c], dp[i][j] + abs(j - c));
                }
            }
        }
    }

    LL ans = 0;
    FOR(j, 0, dp[0].size()) {
        ans = max(ans, dp[D - 1][j]);
    }

    print(ans);

	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int dp[250][150],T[250],x[250][3],D,N,MAX;
main(){memset(dp,-1,sizeof(dp));cin>>D>>N;
for(int i=1;i<=D;i++){cin>>T[i];}
for(int i=1;i<=N;i++){cin>>x[i][0]>>x[i][1]>>x[i][2];if(T[1]>=x[i][0] && T[1]<=x[i][1]){dp[1][x[i][2]]=0;}}
for(int i=2;i<=D;i++){for(int j=1;j<=N;j++){if(T[i]>=x[j][0] && T[i]<=x[j][1]){
for(int k=0;k<=100;k++){dp[i][x[j][2]]=max(dp[i][x[j][2]],dp[i-1][k]+abs(x[j][2]-k));}
}}}
for(int i=0;i<=100;i++){MAX=max(MAX,dp[D][i]);}
cout<<MAX<<endl;}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string.h>

using namespace std;
typedef pair<int, int> P;
int dp[201][201];

void solve()
{
	int D, N;
	cin >> D >> N;
	vector<int> temperature(D);
	for (int i = 0; i < D; ++i)
	{
		cin >> temperature[i];
	}
	vector<P> A(N);
	vector<int> C(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> A[i].first >> A[i].second >> C[i];
	}
	memset(dp, 0, sizeof(dp));
	int ans = 0;
	for (int i = 1; i < D; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			if (A[j].first <= temperature[i] && temperature[i] <= A[j].second)
			{
				for (int k = 0; k < N; ++k)
				{
					if (A[k].first <= temperature[i - 1] && temperature[i - 1] <= A[k].second)
					{
						dp[i][j] = max(dp[i][j], dp[i - 1][k] + abs(C[j] - C[k]));
						ans = max(ans, dp[i][j]);
					}
				}
			}
		}
	}
	cout << ans << endl;
}

int main()
{
	solve();
	return(0);
}

C++: #include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	int d,n;
	int t[210],a[210],b[210],c[210],dp[210][210];
	bool suit[210][210];
	scanf("%d%d",&d,&n);
	for(int i=0;i<d;i++){
		scanf("%d",&t[i]);
	}
	for(int i=0;i<n;i++){
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
	}
	for(int i=0;i<d;i++)for(int j=0;j<n;j++){
		suit[i][j]=(a[j]<=t[i]&&t[i]<=b[j]);
	}
	for(int i=0;i<d;i++)for(int j=0;j<n;j++){
		dp[i][j]=-1;
	}
	for(int j=0;j<n;j++){
		if(suit[0][j])dp[0][j]=0;
	}
	for(int i=0;i<d-1;i++){
		for(int j=0;j<n;j++){
			for(int k=0;k<n;k++){
				if(suit[i+1][k]&&dp[i][j]>=0){
					if(dp[i+1][k]<dp[i][j]+abs(c[j]-c[k])){
						dp[i+1][k]=dp[i][j]+abs(c[j]-c[k]);
					}
				}
			}
		}
	}
	int ans=-1;
	for(int j=0;j<n;j++){
		if(ans<dp[d-1][j])ans=dp[d-1][j];
	}
	printf("%d\n",ans);
	return 0;
}

C++: #include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <iterator>
#include <stack>
typedef long long int lli;
using namespace std;

int abs(int a){
	if(a>0) return a;
	else return -1*a;
}

int dp[201][201];
int main(){
	for(int i=0; i<201; ++i){
		for(int j=0; j<201; ++j){
			dp[i][j]=-1;
		}
	}
	int D,N;
	cin >> D >> N;
	vector<int> tmp(D+1);
	for(int i=1; i<=D; ++i){
		cin >> tmp[i];
	}
	vector<int> c1(N);
	vector<int> c2(N);
	vector<int> c3(N);
	for(int i=0; i<N; ++i){
		cin >> c1[i] >> c2[i] >> c3[i];
	}
	for(int i=0; i<N; ++i){
		for(int j=0; j<N; ++j){
			if(c1[i]<=tmp[1]&&tmp[1]<=c2[i]&&c1[j]<=tmp[2]&&tmp[2]<=c2[j]){
				dp[2][j]=max(dp[2][j],abs(c3[i]-c3[j]));
			}
		}
	}
	for(int i=3; i<=D; ++i){
		for(int j=0; j<N; ++j){
			if(c1[j]<=tmp[i]&&tmp[i]<=c2[j]){
				int tmp=0;
				for(int k=0; k<N; ++k){
					if(dp[i-1][k]!=-1){
						tmp=max(tmp,dp[i-1][k]+abs(c3[j]-c3[k]));
					}
				}
				dp[i][j]=tmp;
			}
		}
	}
	int ans=0;
	for(int i=0; i<N; ++i){
		ans=max(ans,dp[D][i]);
	}
	cout << ans << "\n";
	return 0;
}