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;
#define FOR(i, s, n) for(int i = s; i < (int)n; ++i)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= (int)n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MP make_pair
#define PB push_back
#define EACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define NCLR(a) memset((a), -1 ,sizeof(a))
#define sq(n) (n) * (n)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef priority_queue<int> maxpq;
typedef priority_queue< int, vector<int>, greater<int> > minpq;
typedef complex<double> Point;
static const double EPS = 1e-10;
static const double PI = acos( -1.0 );
static const int mod = 1000000007;
static const int INF = 1 << 29;
static const LL LL_INF = 1ll << 60;
static const int dx[] = { -1, 0, 1, 0, 1, -1, 1, -1 };
static const int dy[] = { 0, -1, 0, 1, 1, 1, -1, -1 };

#ifdef WIN32
#define dump(x) cout << #x << " = " << (x) << "\n"
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << "\n"
#else
#define dump(x)
#define debug(x)
#endif

int d, n;
VI t;
vector<pair<PII, int> > a;
int dp[ 201 ][ 201 ];

void input() {
	cin >> d >> n;
	t.resize( d );
	for ( int i = 0; i < d; i++ ) {
		cin >> t[ i ];
	}
	a.resize( n );
	for ( int i = 0; i < n; i++ ) {
		cin >> a[ i ].first.first >> a[ i ].first.second >> a[ i ].second;
	}
}

int dfs( int now, int k ) {
	if ( now == d ) {
		return 0;
	}
	if ( dp[ now ][ k ] >= 0 ) {
		return dp[ now ][ k ];
	}
	int res = 0;
	if ( now ) {
		for ( int i = 0; i < n; i++ ) {
			if ( t[ now ] >= a[ i ].first.first && a[ i ].first.second >= t[ now ] ) {
				res = max( res, dfs( now + 1, i ) + abs( a[ i ].second - a[ k ].second ) );
			}
		}
	}
	else {
		for ( int i = 0; i < n; i++ ) {
			if ( t[ now ] >= a[ i ].first.first && a[ i ].first.second >= t[ k ] ) {
				res = max( res, dfs( now + 1, i ) );
			}
		}
	}
	return dp[ now ][ k ] = res;
}

void solve() {
	NCLR( dp );
	cout << dfs( 0, 0 ) << "\n";
}

int main() {
  ios::sync_with_stdio( false );
  cin.tie( 0 );
  input();
#ifdef WIN32
  clock_t stime = clock();
#endif
  solve();
#ifdef WIN32
  clock_t etime = clock();
  cout << "TIME : " << ( double ) ( etime - stime ) / CLOCKS_PER_SEC << "\n";
#endif
  return 0;
}

C++: #include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <cassert>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define chmax(a,b) (a<(b)?(a=b,1):0)
#define chmin(a,b) (a>(b)?(a=b,1):0)
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
const int INF = 1<<29;
const double EPS = 1e-8;
const double PI = acos(-1);
typedef pair<int,int> pii;
typedef long long ll;

int dp[201][101];
int T[201];
int A[200];
int B[200];
int C[200];

int main() {
  int d,n;
  while(cin >> d >> n) {
    REP(i,d) cin >> T[i];
    REP(i,n) cin >> A[i] >> B[i] >> C[i];        
    memset(dp,-1,sizeof(dp));
    dp[0][0] = 0;
    REP(i,d) {
      REP(k,101) {
        if (dp[i][k] == -1) continue;      
        REP(j,n) {
          if (A[j]<=T[i] && T[i]<=B[j]) {
            if (i) {
              chmax(dp[i+1][C[j]], dp[i][k] + abs(k-C[j]));
            } else {
              chmax(dp[i+1][C[j]], dp[i][k]);
            }
          }
        }
      }
    }
    int ans = 0;
    REP(i,101) chmax(ans, dp[d][i]);
    cout << ans << endl;
  }
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
const int INF=(1<<21);
int main(){

  typedef struct{
    int a;
    int b;
    int c;
  }wear;
  wear st[200];

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

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

  int dp[d][n];

  for(int i=0;i<d;i++){
    for(int j=0;j<n;j++){
      if(i==0 && st[j].a<=t[0] && st[j].b>=t[0]) dp[i][j]=0;
      else dp[i][j]=-INF;
    }
  }

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

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

  cout<< m<< endl;
}

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

using namespace std;

struct Tshirt{
	int a;
	int b;
	int c;
};

int solve(int,struct Tshirt,int);

int d,n;
int t[201];
int memo[210][210];
struct Tshirt data[201];

int main(){
	cin >> d >> n;
	for(int i=1;i<=d;i++){
		cin >> t[i];
	}
	for(int i=1;i<=n;i++){
		cin >> data[i].a;
		cin >> data[i].b;
		cin >> data[i].c;
	}
	int ans = 0;
	for(int i=1;i<=n;i++){
		if(t[1] >= data[i].a && t[1] <= data[i].b){
			int new_ans=0;
			new_ans = solve(2,data[i],i);
			if(ans < new_ans)ans = new_ans;
		}
	}

	cout << ans  << endl;
	return 0;
}
int solve(int day,struct Tshirt a){
	int rec = 0;
	if(memo[day][a.c] != 0)return memo[day][a.c];
	if(day == d){
		rec = 0;
	}
	for(int i=1;i<=n;i++){
		int o;
		if(t[day] >= data[i].a && t[day] <= data[i].b){
			o = abs(a.c-data[i].c);
			o += solve(day+1,data[i],i);
			rec = max(rec,o);
		}
	}	
	memo[day][a.c] = rec;
	return rec;
}

C++: #include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define int long long
static const int INF = 8931919114514810;
static const int MAX_N = 300;
using namespace std;

int A[300],B[300],C[300];
int mem[MAX_N][MAX_N];
int N,D;
int Day[MAX_N];

int cal(int day,int pp){
   int res=mem[day][pp];
   if(day==N+1){
        return 0;
   }
   if(mem[day][pp]!=-1){
        return mem[day][pp];
   }
    FOR(i,1,D){
        if(Day[day]>=A[i]&&Day[day]<=B[i]){
            if(day==1){
                res=cal(day+1,C[i]);
            }
            else {
                res=max(cal(day+1,C[i])+abs(pp-C[i]),res);
                mem[day][pp]=res;
            }
        }
    }
   return mem[day][pp]=res;
}

signed main(){
    cin>>N>>D;
    fill(mem[0],mem[MAX_N],-1);
    FOR(i,1,N){
        cin>>Day[i];
    }
    FOR(i,1,D){
        cin>>A[i]>>B[i]>>C[i];
    }
    cout<<cal(1,0)<<endl;
    return 0;
}