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 <stdio.h>
#include <algorithm>

int D, N, T[212], A[212], B[212], C[212];
int dp[212][212], memo[212], ans;

int main(void) {
	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) {
			dp[i][j] = -1;
		}
	}
	for (int i = 0; i < D; ++i) {
		for (int j = 0; j < N; ++j) {
			if (A[j] <= T[i] && T[i] <= B[j]) {
				if (i == 0) { dp[i][j] = C[j]; }
				else {
					for (int k = 0; k < N; ++k) {
						if (dp[i - 1][k] != -1) {
							dp[i][j] = dp[i - 1][k] + abs(C[k] - C[j]);
							memo[i] = std::max(memo[i], abs(dp[i][j] - dp[i - 1][k]));
						}
					}
				}
			}
		}
	}

	for (int i = 0; i < D; ++i) {
		ans += memo[i];
	}
	printf("%d\n", ans);
	return 0;
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
int day[200],clo[200][3];
int dp[200][200];
int main(){
  int d,n;
  cin >>d>>n;
  for(int i=0; i<d; i++) cin >>day[i];
  for(int i=0; i<n; i++) for(int j=0; j<3; j++) cin >>clo[i][j];
  for(int i=0; i<d; i++) for(int j=0; j<n; j++) dp[i][j] = -1;
  for(int i=0; i<n; i++) if(clo[i][0]<day[0] && day[0]<clo[i][1]) dp[0][i] = 0;
  for(int i=1; i<d; i++){
    for(int j=0; j<n; j++){
      if(dp[i-1][j] == -1) continue;
      for(int k=0; k<n; k++){
	if(day[i]<clo[k][0] || clo[k][1]<day[i]) continue;
	dp[i][k] = max(dp[i][k],dp[i-1][j]+abs(clo[j][2]-clo[k][2]));
      }
    }
  }
  int ans = 0;
  for(int i=0; i<n; i++) ans = max(ans,dp[d-1][i]);
  cout <<ans<<endl;
  return 0;
}

C++: #include <stdio.h>
#include <algorithm>

int D, N, T[212], A[212], B[212], C[212];
int dp[212][212], ans;

int main(void) {
	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) {
			dp[i][j] = -1;
		}
	}
	for (int i = 0; i < N; ++i) { dp[0][i] = 0; }
	for (int i = 0; i < D; ++i) {
		for (int j = 0; j < N; ++j) {
			if (dp[i][j] >= 0) {
				for (int k = 0; k < N; ++k) {
					if (A[k] <= T[i] && T[i] <= B[k]) {
						dp[i + 1][k] = std::max(dp[i + 1][k], dp[i][j] + abs(C[j] - C[k]));
					}
				}
			}
		}
	}

	ans = -1;
	for (int i = 0; i < D; ++i) {
		ans = std::max(ans, dp[D - 1][i]);
	}
	printf("%d\n", ans + 1);
	return 0;
}

C++: #include <cstdio>
#include <algorithm>

using namespace std;

int main(){
	int i,j,k,most,d,n,x,m;
	int dp[201][201];
	int t[201],a[201],b[201],c[201];

	scanf("%d %d",&d,&n);
	for(i=0;i<d;i++) scanf("%d",&t[i]);
	for(i=0;i<n;i++) scanf("%d %d %d",&a[i],&b[i],&c[i]);
	for(i=0;i<d;i++) for(j=0;j<n;j++) dp[i][j]=-1;
	j=0;
	for(i=0;i<n;i++){
		if(a[i]<=t[0] && t[0]<=b[i]){
			dp[0][j]=i;
			j++;
		}
	}
	x=j;
	for(i=0;i<x;i++){
		for(j=1;j<d;j++){
			most=0;
			for(k=0;k<n;k++){
				if(a[k] <= t[j] && t[j] <= b[k]){
					if(most<abs(c[dp[j-1][i]]-c[k])){
						dp[j][i]=k;
						most=abs(c[dp[j-1][i]]-c[k]);
					}
				}
			}
		}
	}
	for(i=0;i<x;i++){
		for(j=0;j<d;j++) printf("%d ",dp[j][i]);
		printf("\n");
	}
	most=0;
	for(i=0;i<x;i++){
		m=0;
		for(j=1;j<d;j++){
			m+=abs(c[dp[j-1][i]]-c[dp[j][i]]);
		}
		most=max(most,m);
	}
	printf("%d\n",most);
	return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <set>

using namespace std;

#define ALL(co) co.begin(), co.end()

typedef long long LL;
typedef pair<int, int> P;
typedef pair<int, P> IP;
typedef pair<P, P> PP;
typedef vector<int> Array;
typedef vector<int> LArray;

const int INF = 1 << 29;
const LL LINF = 1LL << 60;

int itiv;
inline int getInt() { return (cin >> itiv, itiv); }
void readAll(Array& vec, int n) { for (int i = 0; i < n; i++) cin >> vec[i]; }
inline bool between(int first, int last, int n) { return first <= n && n <= last; }
inline bool inRange(int begin, int end, int n) { return begin <= n && n < end; }
inline bool inRange(int size, int n) { return 0 <= n && n < size; }

int d, n;
int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };
int dr[] = { 0, -1, 0, 1 }, dc[] = { -1, 0, 1, 0 };

int dp[201][201];
int main(void)
{
	while(cin >> d >> n && n)
	{
		Array t(d), c(n);
		vector<P> tem(n);
		readAll(t, d);
		for (int i = 0; i < n; i++)
			cin >> tem[i].first >> tem[i].second >> c[i];
		memset(dp, 0, sizeof(dp));
		int ans = 0;
		for (int i = 1; i < d; i++)
		{
			for (int j = 0; j < n; j++)//今日着る
			{
				if(!between(tem[j].first, tem[j].second, t[i])) continue;
				for (int k = 0; k < n; k++)//昨日着た
				{
					if(!between(tem[k].first, tem[k].second, t[i-1])) continue;
					dp[i][j] = max(dp[i][j], dp[i - 1][k] + abs(c[j] - c[k]));
					ans = max(ans, dp[i][j]);
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

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

using namespace std;

int D,N,t,a,b,c;
vector<int>T,A,B,C;


int func(int i,int p,int res){
  
  if(i==D)return res;

  int mx=0;
  for(int k=0;k<N;k++){
    if(A[k]<=T[i] && T[i]<=B[k] && mx<abs(p-C[k])){
      mx=abs(p-C[k]);
      p=C[k];
    }
  }

  int ans=0;
  for(int j=0;j<N;j++){
    if(mx==abs(p-C[j]))ans=max(ans,func(i+1,p,res+mx));
  }
  return ans;  
}

int main(void){


  while(cin >> D >> N){
    T.clear();
    A.clear();
    B.clear();
    C.clear();
      
    for(int i=0;i<D;i++){
      cin >> t;
      T.push_back(t);
    }

    for(int i=0;i<N;i++){
      cin >> a >> b >> c;
      A.push_back(a);
      B.push_back(b);
      C.push_back(c);
    }

    int ans=0;
    for(int i=0;i<N;i++){
      if(A[i]<=T[0] && T[0]<=B[i]){
	ans=max(ans,func(1,C[i],0));
      }
    }
    cout << ans << endl;
  }

  return 0;
}