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 <iostream>
#include <fstream>
#include <sstream>
#include <iomanip> 
#include <complex> 
#include <string>
#include <vector> 
#include <list>
#include <deque> 
#include <stack> 
#include <queue> 
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <utility>
#include <algorithm> 
#include <numeric> 
#include <typeinfo> 
#include <cstdio>
#include <cstdlib> 
#include <cstring>
#include <cmath>
#include <climits> 
#include <ctime>
using namespace std;

int d,n;
int hot[501];
int a[501],b[501],c[501];
int dp[501][501];
int main(void){
	scanf("%d%d",&d,&n);
	for(int i=0;i<d;i++)scanf("%d",&hot[i]);
	for(int i=0;i<n;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]);
	memset(dp,-1,sizeof(dp));
	for(int i=0;i<n;i++){
		if(a[i]<=hot[0] && hot[0]<=b[i])dp[1][c[i]]=0;
	}
	for(int i=1;i<d;i++){
		for(int j=0;j<200;j++){
			if(dp[i][j]!=-1){
				for(int k=0;k<n;k++){
					if(a[k]<=hot[i] && hot[i]<=b[k]){
						dp[i+1][c[k]]=max(dp[i+1][c[k]],dp[i][j]+abs(c[k]-j));
					}
				}
			}
		}
	}
	int res=0;
	for(int i=0;i<200;i++)res=max(res,dp[d][i]);
	printf("%d\n",res);
	return 0;
}

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

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()

#define PI acos(-1.0)
#define INF 1000000007

typedef long long ll;

ll n, d, p = 0, q, dp;
ll t[1000], a[1000], b[1000], c[1000], MAX[1000], MIN[1000];

int main(){
	cin >> n >> d;
	REP(i, n){
		cin >> t[i];
	}
	REP(i, d){
		cin >> a[i] >> b[i] >> c[i];
	}
	REP(i, n){
		ll ma = -1, mi = 10000;
		REP(j, d){
			if (t[i] >= a[j] && t[i] <= b[j]){
				ma = max(c[j], ma);
				mi = min(c[j], mi);
			}
		}
		MAX[i] = ma;
		MIN[i] = mi;
	}
	if (max(abs(MAX[1] - MAX[0]), abs(MAX[1] - MIN[0])) > max(abs(MIN[1] - MAX[0]), abs(MIN[1] - MIN[0]))){
		dp = MAX[1];
		p = max(abs(MAX[1] - MAX[0]), abs(MAX[1] - MIN[0]));
	}
	else{
		dp = MIN[1];
		p = max(abs(MIN[1] - MAX[0]), abs(MIN[1] - MIN[0]));
	}
	FOR(i, 1, n - 1){
		if (abs(MAX[i + 1] - dp) > abs(MIN[i + 1] - dp)){
			p += abs(MAX[i + 1] - dp);
			dp = MAX[i + 1];
		}
		else{
			p += abs(MIN[i + 1] - dp);
			dp = MIN[i + 1];
		}
	}
	cout << p << endl;
}

C++: #include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
#include <cstdio>
#define INF 100000000

using namespace std;
int dp[205][205] = { 0 }, t[205], a[205], b[205], c[205];
int main(){
	int d, n;
	cin >> d >> n;
	for (int i = 1; i <= d; i++) {
		cin >> t[i];
	}
	for (int j = 1; j <= n; j++) {
		cin >> a[j] >> b[j] >> c[j];
	}
	for (int i = 0; i < 201; i++) {
		for (int j = 0; j < 201; j++) {
			dp[i][j] = -1;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (a[i] <= t[1] && t[1] <= b[i]) dp[1][i] = 0;
	}
	for (int i = 2; i <= d; i++) {
		for (int k = 1; k <= n; k++) {
			for (int j = 1; j <= n; j++) {
				if (a[j] <= t[i] && t[i] <= b[j]&&a[k]<=t[i-1]&&t[i-1]<=b[k]) {
					dp[i][j] = max(dp[i][j], dp[i - 1][k] + abs(c[k] - c[j]));
				}
			}
		}
	}
	int ans = -1;
	for (int i = 1; i <= n; i++) {
		if (ans < dp[d][i]) ans = dp[d][i];
	}
	cout << ans << endl;
	return 0;
}

C++: 
#include <iostream>
#include <math.h>
using namespace std;
int abs(int value){
	if(value>=0)
		return value;
	return -value;
}
int main(){
	int D,N,T[200],A[200][3];
	int dp[200][101];
	cin >> N >> D ;
	for(int i=0;i<N;i++){
		cin >>T[i];
	}
	for(int i=0;i<D;i++){
		for(int j=0;j<3;j++){
			cin >>A[i][j];
		}
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<D;j++){
			dp[i][j]=-9999;
		}
	}
	for(int l=0;l<D;l++){
		if(T[0]>A[l][0] && T[0]<A[l][1] ){
			dp[ 0 ][ A[l][2] ]=0;
			

		}
	}
	for(int i=1;i<N;i++){
		for(int j=0;j<D;j++){
			if(T[i]>=A[j][0] && T[i]<=A[j][1] ){
				for(int l=0;l<=100;l++){
					if(dp[i-1 ][ l ]>=0)
						dp[ i ][ A[j][2] ]=max(dp[ i ][ A[j][2] ],dp[ i-1 ][ l ]+abs(l-A[j][2]));//テ、ツサツ甘」ツ?セテ」ツ?ァテ」ツ?ョテヲツ慊?ゥツォツ佚」ツ??、ツサツ甘・ツ崢?
					

				}
			}
		}
	}
	int answer=0;
	for(int j=0;j<101;j++)
	{
		answer=max(answer,dp[ N-1 ][j]);
	}
	cout << answer << endl;

	return 0;
}

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

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()

#define PI acos(-1.0)
#define INF 1000000007

typedef long long ll;

ll n, d, p = 0, q, dp;
ll t[1000], a[1000], b[1000], c[1000], MAX[1000], MIN[1000];

int main(){
	cin >> n >> d;
	REP(i, n){
		cin >> t[i];
	}
	REP(i, d){
		cin >> a[i] >> b[i] >> c[i];
	}
	REP(i, n){
		ll ma = -1, mi = 10000;
		REP(j, d){
			if (t[i] >= a[j] && t[i] <= b[j]){
				ma = max(c[j], ma);
				mi = min(c[j], mi);
			}
		}
		MAX[i] = ma;
		MIN[i] = mi;
	}
	if (max(abs(MAX[1] - MAX[0]), abs(MAX[1] - MIN[0])) > max(abs(MIN[1] - MAX[0]), abs(MIN[1] - MIN[0]))){
		dp = MAX[1];
		p = max(abs(MAX[1] - MAX[0]), abs(MAX[1] - MIN[0]));
	}
	else{
		dp = MIN[1];
		p = max(abs(MIN[1] - MAX[0]), abs(MIN[1] - MIN[0]));
	}
	FOR(i, 1, n - 1){
		if (abs(MAX[i + 1] - dp) > abs(MIN[i + 1] - dp)){
			p += abs(MAX[i + 1] - dp);
			dp = MAX[i + 1];
		}
		else{
			p += abs(MIN[i + 1] - dp);
			dp = MIN[i + 1];
		}
	}
	cout << p << endl;
}

C++: #include<bits/stdc++.h>
#define INF -1
using namespace std;
int main(){
    int D,N;
    int T[201];
    int A[201],B[201],C[201];
    int dp[201][201]={};
    
    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];
    
    for(int i=0;i<D;i++)
        for(int j=0;j<N;j++) dp[i][j]=INF;
    
    for(int i=0;i<D;i++){
        for(int j=0;j<N;j++){
            if(i==0){
                if(A[j]<=T[i] && T[i]<=B[j]){
                    dp[i][j]=0;
                }
            }
            else if(A[j]<=T[i] && T[i]<=B[j]){
                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=0;
    for(int j=0;j<N;j++) ans=max(ans,dp[D-1][j]);
    
    cout<<ans<<endl;
    
    return 0;
}