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 := 0; 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=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<iostream>
#include<algorithm>
#include<climits>
using namespace std;
static const int MAX_D = 200;
static const int MAX_N = 200;
static const int INF = INT_MAX;

int D, N;
int T[MAX_D];
int A[MAX_N], B[MAX_N], C[MAX_N];
int max_c[MAX_D], min_c[MAX_D];
int memo[2][2][MAX_D];

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];
	
	fill(max_c, max_c + D, 0);
	fill(min_c, min_c + D, INF);
	fill(memo[0][0], memo[2][0], 0);
	for(int i = 0; i < D; i++){
		for(int j = 0; j < N; j++){
			if(A[j] <= T[i] && B[j] >= T[i]){
				max_c[i] = max(max_c[i], C[j]);
				min_c[i] = min(min_c[i], C[j]);
			}
		}
	}
	for(int i = 1; i < D; i++){
		memo[0][0][i] = max(memo[0][0][i - 1], memo[1][0][i - 1]) + abs(max_c[i] - max_c[i - 1]);
		memo[0][1][i] = max(memo[0][0][i - 1], memo[1][0][i - 1]) + abs(min_c[i] - max_c[i - 1]);
		memo[1][0][i] = max(memo[0][1][i - 1], memo[1][1][i - 1]) + abs(max_c[i] - min_c[i - 1]);
		memo[1][1][i] = max(memo[0][1][i - 1], memo[1][1][i - 1]) + abs(min_c[i] - min_c[i - 1]);
	}
	int ans = 0;
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < 2; j++){
			ans = max(ans, memo[i][j][D - 1]);
		}
	}
	
	cout << ans << endl;
	return 0;
}

C++: #include<cstdio>
#include<algorithm>
#define rep(i,a) for(int i=0;i<(a);++i)

const int MAX_D = 200, MAX_N = 200;

int D, N;
int T[MAX_D], A[MAX_N], B[MAX_N], C[MAX_N];

int dp[MAX_D][MAX_N];

bool safe( int d, int k )
{ return A[k] <= T[d] && T[d] <= B[k]; }

int main()
{
	scanf( "%d%d", &D, &N );
	rep( i, D )
		scanf( "%d", T+i );
	rep( i, N )
		scanf( "%d%d%d", A+i, B+i, C+i );

	rep( i, D-1 ) rep( j, N ) if( safe(i,j) ) rep( k, N ) if( safe(i+1,k) )
		dp[i+1][k] = std::max( dp[i+1][k], dp[i][j]+abs(C[k]-C[j]) );

	printf( "%d\n", *std::max_element( dp[D-1], dp[D-1]+N ) );

	return 0;
}

C++: // 基本テンプレート
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

int temp[210], A[210], B[210], C[210];
int dp[210][210];
signed main() {
    int D, N; cin >> D >> N;
    for(int i=0; i<D; i++) {
        cin >> temp[i];
    }
    for(int i=0; i<N; i++) {
        cin >> A[i+1] >> B[i+1] >> C[i+1];
    }

    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for(int i=0; i<D; i++) {
        for(int j=0; j<=N; j++) {
            if(dp[i][j] < 0) continue;
            for(int k=1; k<=N; k++) {
                if(A[k] <= temp[i] and temp[i] <= B[k]) {
                    if(i == 0) chmax(dp[i+1][k], dp[i][j]);
                    else chmax(dp[i+1][k], dp[i][j] + abs(C[j] - C[k]));
                }
            }
        }
    }

    int ans = 0;
    for(int i=0; i<=N; i++) ans = max(ans, dp[D][i]);
    cout << ans << endl;
    return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<cmath>
#define INF 1<<28
using namespace std;

int a[222], b[222], c[222];
int d, n;
int t[222];
int memo[222][222];
int fulele;

int solve(int p, int q){
  if(p == d-1) return 0;
  if(memo[p][q]) return memo[p][q];
  
  int ret = -INF;
  for(int i=0;i<n;i++) 
    if(a[i] <= t[p+1] && t[p+1] <= b[i])
      ret = max(solve(p+1, i)+abs(c[q]-c[i]), ret);
  
  return memo[p][q] = 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];
  
  int ans = -INF;
  for(int i=0;i<n;i++)
    if(a[i] <= t[0] && t[0] <= b[i])
      ans = max(solve(0, i), ans);
  
  cout << ans << endl;
}

C++: #include <algorithm>
#include <iostream>
#include <array>
#include <vector>
#include <cmath>
using namespace std;
 
const int D=200;
const int N=200;
 
struct Clothes{
    int max_t;
    int min_t;
    int c;
};
 
int main(){
    int d,n;
    array<array<int,N>,D> dp;
    vector<Clothes> clt;
    vector<int> tmp;
 
    cin>>d>>n;
 
    tmp.resize(d);
 
    for( auto &t : tmp ) cin>>t;
 
    clt.resize(n);
 
    for( auto &t : clt ) cin>>t.min_t>>t.max_t>>t.c;
 
    for( auto &x : dp ){
        for( auto &y : x ){
            y=0;
        }
    }
 
    for( int i=1 ; i<d ; i++ ){
        for( int j=0 ; j<n ; j++ ){
            if( tmp[i] >= clt[j].min_t && tmp[i] <= clt[j].max_t ){
                for( int k=0 ; k<n ; k++){
                    if( tmp[i-1] >= clt[k].min_t && tmp[i-1] <= clt[k].max_t ){
                        dp[i][j]=max(dp[i][j],abs(clt[j].c-clt[k].c)+dp[i-1][k]);
                    }
                }
            }
        }
    }
 
    cout << accumulate(dp[d-1].begin(),dp[d-1].begin()+n,0,[](int a,int b){ return ( a>b ? a : b ); }) <<endl;
 
    return 0;
}