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>
using namespace std;

struct uyu{int a, b, c;};

int d, n;
int t[202];
vector<uyu> po;

int dp[202][101];

int dfs(int i, int cost, int front)
{
  int &ret = dp[i][front];
  
  if (ret != -1) return ret;
  if (i == d) return cost;
  if (i == 0){
    for (auto &j : po){
      if (t[i] < j.a || j.b < t[i]) continue;
      ret = max(ret, dfs(i + 1, 0, j.c));
    }
    return ret;
  }

  for (auto &j :po){
    if (t[i] < j.a || j.b < t[i]) continue;
    ret = max(ret, dfs(i + 1, cost + abs(front - j.c), j.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(0, 0, 0) << endl;
}

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

int main() {
	int D, N;
	cin >> D >> N;
	int t[D], a[N], b[N], c[N];
	for (int i = 0; i < D; i++) cin >> t[i];
	for (int i = 0; i < N; i++) cin >> a[i] >> b[i] >> c[i];
	int dp[D][N];
    for (int i = 0; i < D; i++) {
		for (int j = 0; j < N; j++) {
          dp[i][j] = 0;
        }
    }
	bool dq[D][N];
	for (int i = 0; i < D; i++) {
		for (int j = 0; j < N; j++) {
			if (t[i] >= a[j] && t[i] <= b[j]) {
				dq[i][j] = true;
			}
			else {
				dq[i][j] = false;
			}
		}
	}
	for (int i = 1; i < D; i++) {
		for (int j = 0; j < N; j++) {
			if (dq[i][j]) {
				for (int k = 0; k < N; k++) {
					if (dq[i - 1][k]) {
						int x = abs(c[j] - c[k]);
						dp[i][j] = max(dp[i][j], dp[i - 1][k] + x);
					}
				}
			}
		}
	}
  int ans = 0;
	for (int i = 0; i < N; i++) {
	  ans = max(ans, dp[D-1][i]);
	}
  cout << ans << endl;
}

C++: #include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
typedef struct {
	int a,b,c;
} HUKU;
int dfs(int day,int now);
HUKU h[202];
int d,n;
int t[202];
int dp[202][202];
int main(){
	cin >> d >> n;
	for(int i=0;i<d;i++) cin >> t[i];
	for(int i=0;i<n;i++){
		cin >> h[i].a >> h[i].b >> h[i].c;
	}
	for(int i=0;i<=d;i++){
		for(int j=0;j<=200;j++){
			dp[i][j] = -1;
		}
	}
	int ans = 0;
	for(int i=0;i<n;i++){
		if(t[0] >= h[i].a && t[0] <= h[i].b){
			ans = max(ans,dfs(1,h[i].c));
		}
	}
	cout << ans << endl;
}

int dfs(int day,int now){
	if(day == d) return 0;
	if(dp[day][now] != -1) return dp[day][now];
	int ret = 0;
	for(int i=0;i<n;i++){
		if(t[day] >= h[i].a && t[day] <= h[i].b){
			ret = max(ret,dfs(day+1,h[i].c) + abs(h[i].c - now));
		}
	}
	//cout << day << " " << now << " " << ret << endl;
	return dp[day][now] = ret;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <complex>
#include <bits/stdc++.h>
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<iostream>
#include<iomanip>
#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<unordered_map>
#include<queue>
#include<vector>
using namespace std;

//#define int long long
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) {cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) {cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
const int MOD = 1e9 + 7;

#define MAX 10

signed main() {
	//??????dp A<=??????<=B?????¨??? dp[i??\???][j????????????] ?????????
	int D, N; cin >> D >> N;
	int T[MAX] = {};
	rep(i, 0, D)cin >> T[i];
	int A[MAX], B[MAX], C[MAX];
	rep(j, 0, N)cin >> A[j] >> B[j] >> C[j];
	int dp[MAX][MAX] = {};
	fill(dp[0], dp[MAX], -1);
	rep(j, 0, N) {
		if (T[0] < A[j] || B[j] < T[0])continue;
		dp[1][j] = 0;
	}
	rep(i, 1, D) {
		rep(j, 0, N) {
			if (T[i] < A[j] || B[j] < T[i])continue;
			rep(k, 0, N) {
				if (dp[i][k] == -1)continue;
				dp[i + 1][j] = max(dp[i + 1][j], dp[i][k] + abs(C[j] - C[k]));
			}
		}
	}
	cout << *max_element(dp[D], dp[D] + MAX) << endl;;
	return 0;
}

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

#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;
int dp[210][101];

int main() {
  REP(i,210)REP(j,101)dp[i][j]=-1000000000;
  int d,n;
  cin>>d>>n;
  vector<int> t(d);
  REP(i,d)cin>>t[i];
  vector<tuple<int,int,int>> cl;
  REP(i,n){
    int a,b,c;
    cin>>a>>b>>c;
    cl.emplace_back(a,b,c);
  }
  REP(i,d){
    REP(j,n){
      int a,b,c;
      tie(a,b,c)=cl[j];
      if(t[i]<a||t[i]>b) continue;
      REP(k,101){
        if (i) dp[i+1][c] = max(dp[i+1][c], dp[i][k] + abs(c-k));
        else dp[i+1][c] = 0;
      }
    }
  }
  int mx = 0;
  REP(i,101)mx=max(mx,dp[d][i]);
  cout<<mx<<endl;
  return 0;
}