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;
int dp[250][150],T[250],x[250][3],D,N,MAX;
main(){memset(dp,-999999,sizeof(dp));
    cin>>D>>N;
    for(int i=1;i<=D;i++){cin>>T[i];}
    for(int i=1;i<=N;i++){
        cin>>x[i][0]>>x[i][1]>>x[i][2];
        if(T[1]>=x[i][0] && T[1]<=x[i][1]){dp[1][x[i][2]]=0;}
    }
    for(int i=2;i<=D;i++){
        for(int j=1;j<=N;j++){
            if(T[i]>=x[j][0] && T[i]<=x[j][1]){
                for(int k=0;k<=100;k++){
                    dp[i][x[j][2]]=max(dp[i][x[j][2]],dp[i-1][k]+abs(x[j][2]-k));
                }
            }
        }
    }
    for(int i=0;i<=100;i++){MAX=max(MAX,dp[D][i]);}
    cout<<MAX<<endl;
    return 0;
}

C++: #include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

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

int main(){
    int d,n;
    cin >> d >> n;

    int dig[205];
    rep(i,d) cin >> dig[i];

    Data cl[205];
    rep(i,n) cin >> cl[i].a >> cl[i].b >> cl[i].c;

    int dp[205][205] = {{0}}; //テヲツ慊?・ツセツ古」ツ?ォテァツ敖?」ツ?淌ヲツ慊催」ツ??ヲツ猟・
    memset(dp, -1, sizeof(dp));
    rep(i,n){
        if(cl[i].a <= dig[0] && dig[0] <= cl[i].b){
            dp[i][0] = 0;
        }
    }

    range(i,1,d){
        rep(j,n){
            if(cl[j].a <= dig[i] && dig[i] <= cl[j].b){
                rep(k,n){
                    if(dp[k][i - 1] == -1) continue;
                    dp[j][i] = max(dp[j][i], dp[k][i - 1] + abs(cl[k].c - cl[j].c));
                }
            }
        }
    }

    int maxi = 0;
    rep(i,n){
        maxi = max(maxi, dp[i][d - 1]);
    }
    cout << maxi << endl;
}

C++: #include <bits/stdc++.h>

using namespace std;

int n, d;
int t[200];
int a[200], b[200], c[200];
int dp[201][200]; // dp[i][j] = i??\?????????j???????????????????´????????????¶??????????????§???


int main()
{
    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 = 1; i < d; ++i) {
        for (int j = 0; j < n; ++j) { // i??\???
            if (a[j] <= t[i] && t[i] <= b[j]) {
                for (int k = 0; k < n; ++k) { // i-1??\???
                    if (a[k] <= t[i - 1] && t[i - 1] <= b[k]) {
                        dp[i][j] = max(dp[i][j], dp[i - 1][k] + abs(c[j] - c[k]));
                    }
                }
            }
        }
    }

    int ma = 0;

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

    cout << ma << endl;
}

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; 
typedef pair<ll, ll> PL;

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

int main(){
	cin >> d >> n;
	REP(i, d){
		cin >> t[i];
	}
	REP(i, n){
		cin >> a[i] >> b[i] >> c[i];
	}
	REP(i, d){
		ll ma = -1, mi = 10000;
		REP(j, n){
			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;
	}
	dp1 = 0;
	dp2 = 0;
	REP(i, d - 1){
		dp1 = max(dp1 + abs(MAX[i + 1] - MAX[i]), dp2 + abs(MIN[i + 1] - MAX[i]));
		dp2 = max(dp2 + abs(MAX[i + 1] - MIN[i]), dp1 + abs(MIN[i + 1] - MIN[i]));
	}
	cout << max(dp1,dp2) << endl;
}

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

int dp[61][201], d, n, t[61], a[201], b[201], c[201], mx = 0;

int abs(int x, int y)
{
	if (x >= y) return x - y;
	else return y - x;
}

int main()
{
	cin >> d >> n;
	for (int i = 1; i <= d; i++){
		cin >> t[i];
	}
	for (int i = 1; i <= n; i++){
		cin >> a[i] >> b[i] >> c[i];
	}
	memset(dp, -1, sizeof dp);

	for (int i = 1; i <= n; i++){
		if (a[i] <= t[1] && t[1] <= b[i]){
			dp[1][i] = 0;
		}
	}

	//dp
	for (int today = 2; today <= d; today++){
		for (int n2 = 1; n2 <= n; n2++){
			for (int n1 = 1; n1 <= n; n1++){
				if (dp[today - 1][n1] == -1) continue;
				if (a[n2] > t[today] || t[today] > b[n2]) continue;
				dp[today][n2] = max(dp[today][n2], dp[today - 1][n1] + abs(c[n1], c[n2]));
			}
		}
	}

	for (int i = 1; i < n; i++){
		mx = max(dp[d][i], mx);
	}
	cout << mx << endl;
	return 0;
}

C++: #include <bits/stdc++.h>

using namespace std;

int t[200];
int a[200], b[200], c[200];

int dp[200][200];

int 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];
    }

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

    int ans = 0;

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

    printf("%d\n", ans);
}

C++: #include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define rrep(i,n) for(int (i)=1;i<=(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define MOD 1000000007
#define INF 1e18
#define int long long
#define endl "\n"
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
typedef long long ll;
typedef pair<int, int> P;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a/gcd(a,b)*b;};
int mod(int a,int b){return (a+b-1)/b;};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;};

int dp[220][220];

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	//cout << fixed << setprecision(15);
	
	int D, N;
	cin >> D >> N;
	int 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, D - 1) {
		int tmp = t[i];
		int ntmp = t[i + 1];
		rep(j, N) {
			if(tmp < a[j] || b[j] < tmp) continue;
			rep(k, N) {
				if(a[k] <= ntmp && ntmp <= b[k]) {
					chmax(dp[i+1][k], dp[i][j] + abs(c[j] - c[k]));
				}
			}
		}
	}

	int ans = 0;
	rep(i, N) {
		chmax(ans, dp[D - 1][i]);
	}
	cout << ans << endl;
	return 0;
}