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 <cstdio>
#include <algorithm>

using namespace std;

#define INF (1<<28)
#define MD 200
#define MN 100
int D, N;
int T[MD+1];
int CA[MN+1], CB[MN+1], CC[MN+1];

int solve() {
    int dp[MD+1][MN+1];
    for (int i = 0; i < D; i++) {
        for (int j = 0; j < N; j++) {
            if (CA[j] <= T[i] && T[i] <= CB[j]) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = -1;
            }
        }
    }
    for (int i = 1; i < D; i++) {
        for (int j = 0; j < N; j++) {
            if (dp[i][j] < 0) continue;
            for (int k = 0; k < N; k++) {
                if (CA[k] > T[i-1] || T[i-1] > CB[k]) continue;
                dp[i][j] = max(dp[i][j], dp[i-1][k] + abs(CC[j] - CC[k]));
            }
        }
    }
    int ret = 0;
    for (int i = 0; i < N; i++) {
        ret = max(ret, dp[D-1][i]);
    }
    //for (int i = 0; i < D; i++) {
    //    for (int j = 0; j < N; j++) {
    //        printf("%4d", dp[i][j]);
    //    }
    //    printf("\n");
    //}
    return ret;
}

int main() {
    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", CA+i, CB+i, CC+i);
    printf("%d\n", solve());
    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 T[210], A[210], B[210], C[210];
int dp[210][110];
signed main() {
    int D, N; 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(dp[0], dp[D+1], -1);
    dp[0][0] = 0;
    for(int i=0; i<D; i++) {
        int temp = T[i];
        for(int j=0; j<=100; j++) {
            if(dp[i][j] == -1) continue;
            for(int k=0; k<N; k++) {
                if(A[k] <= temp and temp <= B[k]) {
                    int cost = (i == 0 ? 0 : abs(j - C[k]));
                    chmax(dp[i+1][C[k]], dp[i][j] + cost);
                }
            }
        }
    }

    cout << *max_element(dp[D], dp[D] + 101) << endl;
    return 0;
}

C++: #include<bits/stdc++.h>
#define LL long long
#define FOR(i,a,b) for(int i=a;i<=b;++i)

using namespace std;

static const LL MAX_N = 1e+5;
static const LL INF = 1 << 25;

struct clothes{
    LL A[100],B[100],C[150];
};

int N,D;
LL res=-INF;
LL Day[300];
LL mem[300][100000];
clothes T;
int i;

LL cal(LL day,LL p,LL pp,LL sum){
    //cout<<res<<" "<<day<<endl;
    if(res<sum+abs(pp-p)&&day==N+1){
        return mem[day][sum+abs(pp-p)]=res=sum+abs(pp-p);
    }
    else if(mem[day][sum+abs(pp-p)]!=0){
           // cout<<"hoge"<<endl;
        return mem[day][sum+abs(pp-p)];
    }
    else{
        if(day==N+1)return 0;
        else if(day==0){
            FOR(i,1,D)
            if(Day[1]>=T.A[i]&&Day[1]<=T.B[i])cal(day+1,T.C[i],p,sum);
        }
        FOR(i,1,D){
            if(Day[day]>=T.A[i]&&Day[day]<=T.B[i]){
                if(day>2)cal(day+1,T.C[i],p,sum+abs(pp-p));
                else cal(day+1,T.C[i],p,sum);
            }
        }
    }
    return res;
}


int main(){
    cin>>N>>D;
    FOR(i,1,N)cin>>Day[i];
    FOR(i,1,D)
        cin>>T.A[i]>>T.B[i]>>T.C[i];
    cout<<cal(0,0,0,0)<<endl;
}

C++: #include <iostream>
#include <algorithm>
using namespace std;

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

int main(){
  int d,n;
  while(cin >> d >> n){
    int t[200],dp[200][200],ans=0;
    data v[200];
    for(int i=0;i<d;i++) cin >> t[i];
    for(int i=0;i<n;i++) cin >> v[i].a >> v[i].b >> v[i].c;

    fill(dp[0],dp[200],0);
    for(int i=1;i<d;i++){
      for(int j=0;j<n;j++){
        if(v[j].a > t[i-1] || v[j].b < t[i-1]) continue;
        for(int k=0;k<n;k++){
          if(v[k].a > t[i] || v[k].b < t[i]) continue;
          dp[i][k] = max(dp[i][k], dp[i-1][j] + abs(v[j].c-v[k].c));
        }
      }
    }
    for(int i=0;i<n;i++) ans = max(ans,dp[d-1][i]);
    cout << ans << endl;
  }
}

C++: #include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;

int main(){
  int memo_tf[222][222]={};
  int memo[222][222]={};
  int A[222],B[222],C[222],T[222];
  int N,D;
  int ab[222][222]={};

  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++){
      if(A[j]<=T[i] && T[i]<=B[j]){
	memo_tf[i][j]=1;
      }
    }
  }
  
  int sum=0;

  for(int i=1;i<D;i++){
    for(int j=0;j<N;j++){
      if(memo_tf[i][j]==1){
	int max=0;
	for(int k=0;k<N;k++){
	  if(memo_tf[i-1][k]==1){
	    if(ab[k][j]==0){
	      ab[k][j]=abs(C[k]-C[j]);
	      ab[j][k]=ab[k][j];
	    }
	    if(max<(memo[i-1][k]+ab[k][j])){
	      max=memo[i-1][k]+ab[k][j];
	    }
	  }
	}
	memo[i][j]=max;
      }
      if(sum<memo[i][j]){
	sum=memo[i][j];
      }
    }
  }

  /*
  for(int i=0;i<D;i++){
    for(int j=0;j<N;j++){
      printf("%2d ",memo[i][j]);
    }
    printf("\n");
  }
  */  

  printf("%d\n",sum);


  return 0;
}

C++: #include <iostream>
#include <cmath>
using namespace std;

int main(){
	int D,N;
	cin>>D>>N;
	int T[D],A[N],B[N],C[N];
	for(int d=0; d<D; ++d)	cin>>T[d];
	for(int n=0; n<N; ++n)	cin>>A[n]>>B[n]>>C[n];
	int dp[D][N];
	for(int n=0; n<N; ++n)	dp[0][n]=(A[n]<=T[0]&&T[0]<=B[n]? 0: -(1<<29));
	for(int d=1; d<D; ++d)for(int n=0; n<N; ++n)	dp[d][n]=-(1<<29);
	for(int d=1; d<D; ++d)for(int n=0; n<N; ++n)for(int i=0; i<N; ++i){
		if(A[i]<=T[d]&&T[d]<=B[i])	dp[d][i]=max(dp[d][i], dp[d-1][n]+abs(C[n]-C[i]));
	}
	int ans=0;
	for(int i=0; i<N; ++i)	ans=max(ans, dp[D-1][i]);
	cout << ans << endl;
}