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;

int main(void) {
  int d, n;
  cin >> d >> n;

  vector<int> t(d);
  for (int i = 0; i < d; i++) {
    cin >> t[i];
  }

  vector<int> a(n), b(n), c(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i] >> c[i];
  }

  int dp[210][210];
  fill(dp[0], dp[210], -1);
  for (int i = 0; i < n; i++) {
    if (a[i] <= t[0] && t[0] <= b[i]) {
      dp[0][i] = 0;
    }
  }

  for (int i = 1; i < d; i++) {
    for (int j = 0; j < n; j++) {
      if (!(a[j] <= t[i] && t[i] <= b[j])) continue;
      for (int k = 0; k < n; k++) {
        if (dp[i - 1][k] < 0) continue;
        dp[i][j] = max(dp[i][j], dp[i - 1][k] + abs(c[j] - c[k]));
      }
    }
  }

  int ans = -1;
  for (int i = 0; i < n; i++) {
    ans = max(ans, dp[d - 1][i]);
  }

  cout << ans << endl;

  return 0;
}

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

int D,N;
int T[200];
int A[200],B[200],C[200];

int memo[200][101];
int calc(int d,int p){
    if(d==D){return 0;}
    if(~memo[d][p])return memo[d][p];

    int ret=0;
    for(int i=0;i<N;i++){
        if(A[i]>T[d]||B[i]<T[d])continue;
        ret=max(ret,calc(d+1,C[i])+(d?abs(C[i]-p):0));
    }

    return memo[d][p]=ret;
}

int main(){
    cin>>D>>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];

    memset(memo,-1,sizeof(memo));
    cout<<calc(0,0)<<endl;
    return 0;
}

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

int d, n;
int t[202];
int a[202], b[202], c[202];

int dp[256][256][20020];

int dfs(int i=0, int front=0, int cost=0)
{
  int &ret = dp[i][front][cost];
  if (ret != -1) return ret;
  if (i == d) return cost;

  for (int j = 0; j < n; j++){
    if (t[i] < a[j] || b[j] < t[i]) continue;
    ret = max(dfs(i + 1, j, (i ? cost + abs(c[front] - c[j]) : 0)), ret);
  }

  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++){
    cin >> a[i] >> b[i] >> c[i];
  }

  cout << dfs() << endl;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#define INF (1<<30)
using namespace std;
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int D, N; cin >> D >> N;
	vector<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];
	vector<vector<pair<int, int>>> dp(D, vector<pair<int, int>>(N, { 0,-1 }));

	int ans = 0;
	for (int i = 0; i < N;i++) {
		if (T[0] >= A[i] && T[0] <= B[i]) {
			dp[0][i] = { 0,C[i] };
		}
	}

	for (int i = 1; i < D;i++) {
		for (int j = 0; j < N;j++) {
			if (T[i] >= A[j] && T[i] <= B[j]) {
				for (int k = 0; k < N;k++) {
					if (dp[i - 1][k].second != -1) {
						if (dp[i][j].first <= dp[i - 1][k].first + abs(C[j] - dp[i - 1][k].second)) {
							dp[i][j].first = dp[i - 1][k].first + abs(C[j] - dp[i - 1][k].second);
							dp[i][j].second = C[j];
						}
					}
				}

			}
		}
	}
	for (int i = 0; i < N;i++) {
		ans = max(ans, dp[D - 1][i].first);
	}
	cout << ans << endl;
}

C++: #include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
 
using namespace std;
 
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) r.begin(),r.end()
#define fi first
#define se second
#define println(X) cout<<X<<endl;
#define DBG(X) cout<<#X<<" : "<<X<<endl;
 
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-10;


int dp[210][210];


int main(){
	int d, n;
	cin>>d>>n;
	vi t(d);
	rep(i, d) cin>>t[i];
	vi a(n), b(n), c(n);
	rep(i, n) cin>>a[i]>>b[i]>>c[i];

	rep(i ,210) rep(j, 210) dp[i][j] = -1;

	for(int i = 0; i < n; i++){
		if(a[i] <= t[0] && t[0] <= b[i]){
			dp[0][i] = 0;
		}
	}

	for(int i = 1; i < d; i++){
		for(int j = 0; j < n; j++){
			if(a[j]<=t[i] && t[i] <=b[j]){
				for(int k = 0; k < n; k++){
					if(dp[i-1][k] != -1){
						dp[i][j] = max(dp[i][j], dp[i-1][k] + abs(c[k]-c[j]));
					}
				}
			}
		}
	}
	int ans = 0;
	rep(i, 210){
		ans = max(ans, dp[d-1][i]);
	}
	cout<<ans<<endl;
}

C++: // 2014/11/12 Tazoe

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
	int D, N;
	cin >> D >> N;

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

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

	int DP[200][200];

	for(int j=0; j<N; j++){
		if(A[j]<=T[0] && T[0]<=B[j]){
			DP[0][j] = 0;
		}
		else{
			DP[0][j] = -1;
		}
	}

	for(int i=1; i<D; i++){
		for(int j=0; j<N; j++){
			if(!(A[j]<=T[i] && T[i]<=B[j])){
				DP[i][j] = -1;
				continue;
			}

			DP[i][j] = 0;
			for(int k=0; k<N; k++){
				if(DP[i-1][k]==-1)
					continue;

				DP[i][j] = max(DP[i][j], DP[i-1][k]+abs(C[j]-C[k]));
			}
		}
	}

	int DP_max = -1;
	for(int j=0; j<N; j++){
		DP_max = max(DP_max, DP[D-1][j]);
	}

	cout << DP_max << endl;

	return 0;
}

C++: #include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const long long INF = 1e9;

int main(){
  int D, N;
  cin >> D >> N;
  vector<int> T(D);
  for(int i = 0; i < D; ++i){
    cin >> T[i];
  }
  vector<int> A(N), B(N), C(N);
  for(int i = 0; i < N; ++i){
    cin >> A[i] >> B[i] >> C[i];
  }
  int M = *max_element(C.begin(), C.end())+1;
  vector<int> dp(M,-INF);
  for(int i = 0; i < M; ++i){
    for(int j = 0; j < N; ++j){
      if(T[0] < A[j] or T[0] > B[j]) continue;
      dp[C[j]] = 0;
    }
  }
  for(int i = 1; i < D; ++i){
    vector<int> dp_(M,-INF);
    for(int j = 0; j < N; ++j){
      if(T[i] < A[j] or T[i] > B[j]) continue;
      for(int k = 0; k < M; ++k){
        dp_[C[j]] = max(dp_[C[j]],dp[k]+abs(k-C[j]));
      }
    }
    dp = dp_;
  }
  cout << *max_element(dp.begin(), dp.end()) << endl;
}