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 <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;

int n, d, p = 0, q;
int t[1000], a[1000], b[1000], c[1000];
vector< pair<int,int> > vpi;

int main(){
	cin >> n >> d;
	REP(i, n){
		cin >> t[i];
	}
	REP(i, d){
		cin >> a[i] >> b[i] >> c[i];
	}
	REP(i, n){
		int max = -1, min = 10000;
		REP(j, d){
			if (t[i] >= a[j] && t[i] <= b[j]){
				if (max < c[j])max = c[j];
				if (min > c[j])min = c[j];
			}
		}
		vpi.push_back(make_pair(max, min));
	}
	REP(i, vpi.size() - 1){
		int a = abs(vpi[i + 1].first - vpi[i].first);
		a = max(a, abs(vpi[i + 1].second - vpi[i].first));
		a = max(a, abs(vpi[i + 1].first - vpi[i].second));
		a = max(a, abs(vpi[i + 1].second - vpi[i].second));
		p += a;
	}
	cout << p << endl;
}

C++: #include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<sstream>


#define reps(i,f,n) for(int i = f; i < int(n); i++)
#define rep(i,n) reps(i,0,n)

#define PII pair<int,int>
#define PP pair< int,PII >


using namespace std;

int dp[256][256];
int c[256];
int t[256];
int a[256];
int b[256];

int main(){
	
	int n,d;
	scanf("%d%d", &d, &n);
	rep(i,d)scanf("%d", &t[i]);
	rep(i,n)scanf("%d%d%d", &a[i], &b[i], &c[i]);
	
	rep(i,256)rep(j,256)dp[i][j] = -1;
	
	dp[0][0] = 0;
	
	
	rep(i,d)rep(j,128){
		if(dp[i][j] != -1){
			rep(k,n){
				if(a[k] <= t[i] && t[i] <= b[k]){
					if(i == 0)dp[i+1][c[k]] = 0;
					else dp[i+1][c[k]] = max(dp[i+1][c[k]], dp[i][j] + abs(j-c[k]));
				}
			}
		}
	}
	
	int ans = 0;
	rep(j,d+1){
		rep(i,128){
			ans = max(ans, dp[j][i]);
		}
	}
	
	
	printf("%d\n", ans);
	
	return 0;
}

C++: #include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
#define max 1000
int d,n;
int t[max],a[max],b[max],c[max];
bool suit[max][max];
int dp[max][max];
int main(){
    cin>>d>>n;
    for(int i=0;i<d;i++){
      cin>>t[i];
    }
    for(int j=0;j<n;j++){
      cin>>a[j]>>b[j]>>c[j];
    }
    for(int i=0;i<d;i++){
      for(int j=0;j<n;j++){
        suit[i][j]=(t[i]>=a[j]&&t[i]<=b[j]);
      }
    }
    memset(dp,-1,sizeof(dp));
    for(int j=0;j<n;j++){
      if(suit[0][j]==true){
       dp[0][j]=0;
     }
    }
    for(int i=0;i<d-1;i++){
      for(int j=0;j<n;j++){
        if(dp[i][j]>=0) {
           for(int k=0;k<n;k++){
             if(suit[i+1][k]==true){
               if(dp[i+1][k]<dp[i][j]+abs(c[j]-c[k])){
                 dp[i+1][k]=dp[i][j]+abs(c[j]-c[k]);
               }
             }
           }
        }
      }
    }
    int ans=-1;
    for(int j=0;j<n;j++){
      if(dp[d-1][j]>ans){
        ans=dp[d-1][j];
      }
    }
    cout<<ans<<endl;
  return 0;
}

C++: #include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt" > "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\b.answer"

struct clo {
	int amin;
	int amax;
	int value;
};

int main() {
	int D, N; cin >> D >> N;
	vector<int>ts;
	for (int i = 0; i < D; ++i) {
		int t; cin >> t; ts.emplace_back(t);
	}
	vector<clo>cs;
	for (int i = 0; i < N; ++i) {
		int a, b, c; cin >> a >> b >> c;
		cs.push_back(clo{ a,b,c });
	}
	vector<vector<int>>dp(D + 1, vector<int>(N,-1e9));
	for (int i = 0; i < N; ++i) {
		dp[0][i] = 0;
	}
	for (int d = 0; d < D; ++d) {
		const int hot = ts[d];
		for (int f = 0; f < N; ++f) {
			const int prevalue = cs[f].value;
			for (int c = 0; c < N; ++c) {
				if (cs[c].amin <= hot&&hot <= cs[c].amax) {
					const int nowvalue = d?cs[c].value:cs[f].value;
					dp[d + 1][c] = max(dp[d + 1][c], dp[d][f] + abs(prevalue - nowvalue));
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < N; ++i) {
		ans = max(ans, dp[D][i]);
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

typedef struct {
	int a;
	int b;
	int c;
} fuku_t;

int d, n;

int t[200];
fuku_t fuku[200];

int dp[200][200];

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

	for (int i = 0; i < d; ++i) cin >> t[i];

	for (int i = 0; i < n; ++i) scanf("%d %d %d", &fuku[i].a, &fuku[i].b, &fuku[i].c);

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

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

	int ans = 0;

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

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

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

constexpr int INF = 1 << 30;

void solve() {
    int d, n;
    std::cin >> d >> n;

    std::vector<int> ts(d);
    for (auto& t : ts) std::cin >> t;

    std::vector<int> ls(n), rs(n), cs(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> ls[i] >> rs[i] >> cs[i];
    }

    std::vector<int> dp(n, -INF);
    {
        for (int i = 0; i < n; ++i) {
            if (ls[i] <= ts[0] && ts[0] <= rs[i]) dp[i] = 0;
        }
    }

    auto ndp = dp;
    for (int j = 1; j < d; ++j) {
        std::fill(ndp.begin(), ndp.end(), -INF);

        for (int i = 0; i < n; ++i) {
            if (ts[j] < ls[i] || rs[i] < ts[j]) continue;
            for (int pi = 0; pi < n; ++pi) {
                ndp[i] = std::max(ndp[i], dp[pi] + std::abs(cs[i] - cs[pi]));
            }
        }

        std::swap(dp, ndp);
    }

    std::cout << *std::max_element(dp.begin(), dp.end()) << "\n";
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}