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;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF    	((ll)1ll<<60)
#define INF     	((int)1<<30)
#define EPS     	(1e-9)
#define MOD     	(1000000007ll)
#define fcout(a)	cout<<setprecision(a)<<fixed
#define fs 			first
#define sc			second
#define PI			3.1415926535897932384

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s; a=0;} return os;}
void OUT(bool b){cout<<(b?"YES":"NO")<<endl;}
void Out(bool b){cout<<(b?"Yes":"No")<<endl;}
void out(bool b){cout<<(b?"yes":"no")<<endl;}
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int clz(int x) { return 31 - __builtin_clz(x); }
int clz(ll x) { return 63 - __builtin_clzll(x); }
int ctz(int x) { return __builtin_ctz(x); }
int ctz(ll x) { return __builtin_ctzll(x); }

class compare {
public:
	bool operator()(tuple<ll, ll> a, tuple<ll, ll> b) {
		return (get<1>(a) > get<1>(b));
	}
};

int dp[201][201];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,d;
	//dp[last][day]
	cin>>d>>n;
	vi t(d),a(n),b(n),c(n);
	rep(i,d)cin>>t[i];
	rep(i,n)cin>>a[i]>>b[i]>>c[i];
	rep(i,201){
		rep(j,201){
			dp[j][i]=-1;
		}
	}
	rep(i,d){
		rep(j,n){
			rep(k,n){
				if(a[k]<=t[i]&&t[i]<=b[k]){
					dp[k][i+1]=max(dp[k][i+1],dp[j][i]+((dp[j][i]!=-1)?abs(c[j]-c[k]):1));
				}
			}
		}
	}
	int ans=0;
	rep(i,n){
		ans=max(ans,dp[i][d]);
	}
	cout<<ans<<endl;
}

C++: #include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n;i>=0;i--)
#define INF 100000005
#define MAX 100000001
#define dmp make_pair
#define dpb push_back
#define fi first
#define se second
using namespace std;
//__gcd(a,b), __builtin_popcount(a);

int a[201], b[201][3];
pair<int,int> dp[201][2];
int main(){
	int d, n, ans = 0;
	scanf("%d%d", &d, &n);
	rrep(i,d)scanf("%d", &a[i]);
	rrep(i,n)scanf("%d%d%d", &b[i][0], &b[i][1], &b[i][2]);
	int t1, t2;
	for(int i = 1;i <= d;i++){
		t1 = INF;t2 = 0;
		for(int j = 1;j <= n;j++){
			if(b[j][0] <= a[i] && a[i] <= b[j][1]){
				t1 = min(t1, b[j][2]);
				t2 = max(t2, b[j][2]);
			}
		}
		dp[i][0].se = t1;
		dp[i][1].se = t2;
		dp[i][0].fi = dp[i-1][1].fi + abs(dp[i-1][1].se-t1);
		dp[i][1].fi = dp[i-1][0].fi + abs(t2-dp[i-1][0].se);
		if(i == 1){
			dp[i][0].fi = 0;
			dp[i][1].fi = 0;
		}
	}
	t1 = dp[d][0].fi;
	t2 = dp[d][1].fi;
	ans = max(t1, t2);
	printf("%d\n", ans);
	return 0;
}

C++: #include <iostream>
#include <cmath>
using namespace std;
int tem[201],G[201][3],D,N,DP[201][201]={0};
	
int main() {
	cin >> D >> N ;
	for (int i=1;i<=D;i++){
		cin>>tem[i];
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<3;j++){
			cin >> G[i][j];

		}
		if(!(G[i][0]<=tem[1] && tem[1]<=G[i][1]))
			DP[i][1]=-9999;
	}

	for(int i=2;i<=D;i++){
		for(int j=0;j<N;j++){
			if(G[j][0]<=tem[i] && tem[i]<=G[j][1]){
			for(int k=0;k<N;k++){
			DP[j][i]=max(DP[j][i],DP[k][i-1]+abs(G[k][2]-G[j][2]));
			}
			}
		}
	}
	int maxer=-1;
	for (int i=0;i<N;i++){
		maxer=max(maxer,DP[i][D]);
	}
	cout << maxer << endl; 
}

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

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

int dp[256][256] = { 0 };

int main(){
    int d,n;
    cin >> d >> n;
    int t[256];
    for(int i = 1; i <= d; i++){
        cin >> t[i];
    }
    CLOTHES clo[256];
    for(int i = 1; i <= n; i++){
        cin >> clo[i].a >> clo[i].b >> clo[i].c;
    }
    
    int maxi = 0, sum = 0;
    for(int i = 1; i <= d; i++){
        maxi = 0;
        for(int i2 = 1; i2 <= n; i2++){
            if(t[i] >= clo[i2].a && t[i] <= clo[i2].b){
                for(int j = 1; j <= n; j++){
                    if(dp[i - 1][j] != -1){
                        dp[i][i2] = max(dp[i][i2], abs(clo[j].c - clo[i2].c));
                    }
                }
            }
            else{ dp[i][i2] = -1; }
            maxi = max(maxi,dp[i][i2]);
        }
        if(i != 1){ sum += maxi; }
    }

    cout << sum << endl;
}

C++: #include <iostream>
#include<limits.h>
#include<algorithm>
#include<math.h>
using namespace std;
 
int main() {
int day,manycloth;
cin>>day>>manycloth;
int kion[200];
for(int i = 0;i<day;i++){cin>>kion[i];}
int cloth[200][3];
for(int i = 0;i<manycloth;i++){
	for(int j=0;j<3;j++){
		cin>>cloth[i][j];
	}
}
int dp[201][200];
for(int i = 0;i<201;i++){for(int j= 0;j<200;j++){dp[i][j]=INT_MIN;}}
for(int i=0;i<200;i++){dp[0][i]=0;}
for(int i = 0;i<=day;i++){
	for(int j =0;j<manycloth;j++){
		if(cloth[j][0]>kion[i] or cloth[j][1]<kion[i]){
			dp[i][j]=-1;}
		else{
			if(i!=0){
				for(int h= 0;h<manycloth;h++){
					if(dp[i-1][h]!=-1){
						dp[i][j]=max(dp[i][j],dp[i-1][h]+abs(cloth[h][2]-cloth[j][2]));
					}
				}
			}
		}
	}
}
int ans = INT_MIN;
for(int i =0;i<manycloth;i++){
if(ans<dp[day-1][i]){ans=dp[day-1][i];}
}
cout<<ans<<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[MAX_N],B[MAX_N],C[MAX_N];
};

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

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