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

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

// dp[i,j] := ?????\??????j??????????????????,
//			  i??\????????§????´??????????????????¶?????????????¨?????????§???

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

	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < N; ++i) {
		if (A[i] <= T[0] && T[0] <= B[i]) { dp[0][i] = 0; }
	}
	for (int i = 1; i < D; ++i) {
		for (int j = 0; j < N; ++j) {
			if (dp[i - 1][j] != -1) {
				for (int k = 0; k < N; ++k) {
					if (A[k] <= T[i] && T[i] <= B[k]) {
						dp[i][k] = std::max(dp[i][k], dp[i - 1][j] + abs(C[k] - C[j]));
					}
				}
			}
		}
	}

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

C++: #include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
using namespace std;

#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int main(){
  int d, n;
  cin >> d >> n;
  vector<int> t(d);
  rep(i,d) cin >> t[i];
  vector<int> a(n), b(n), c(n);
  rep(i,n) cin >> a[i] >> b[i] >> c[i];
  vector<vector<int>> dp(d,vector<int>(n,-1));
  rep(i,n){
    if(a[i]<=t[0] && b[i]>=t[0])
      dp[0][i] = 0;
  }
  for(int i=1; i<d; i++){
    rep(j,n){
      if(a[j]<=t[i] && b[j]>=t[i]){
        rep(k,n){
          if(dp[i-1][k]!=-1)
            chmax(dp[i][j], dp[i-1][k]+abs(c[k]-c[j]));
        }
      }
    }
  }
  int ans=0;
  rep(i,n) ans = max(ans, dp[d-1][i]);
  cout << ans << endl;
  return 0;
}

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

struct str
{
	int a, b, c;
};
int t[200];
str b[200];
str dp[200];
int main(){
	int d, n;
	scanf("%d%d", &d, &n);
	for (int i = 0; i < d; i++)
		scanf("%d", &t[i]);
	for (int i = 0; i < n; i++){
		int a_, b_, c_;
		scanf("%d%d%d", &a_, &b_, &c_);
		b[i].a = a_;
		b[i].b = b_;
		b[i].c = c_;
	}
	int min = 101;
	for (int i = 0; i < n; i++)
		if (b[i].a <= t[0] && t[0] <= b[i].b&&min > b[i].c)
			min = b[i].c;
	dp[0].a = 0; dp[0].b = min;
	for (int i = 1; i < d; i++){
		int max = 0;
		for (int j = 0; j < n; j++){
			if (b[j].a <= t[i] && t[i] <= b[j].b&&abs(dp[i - 1].b - b[j].c) >= max){
				max = abs(dp[i - 1].b - b[j].c);
				dp[i].b = b[j].c;
			}
		}
		dp[i].a = dp[i - 1].a + max;
	}
	printf("%d\n", dp[d - 1]);
	return 0;
}

C++: #include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
 
using namespace std;
 
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) r.begin(),r.end()
#define fi first
#define se second
#define println(X) cout<<X<<endl;
#define DBG(X) cout<<#X<<" : "<<X<<endl;
 
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-10;


int dp[210][210];


int main(){
	int d, n;
	cin>>d>>n;
	vi t(d);
	rep(i, d) cin>>t[i];
	vi a(n), b(n), c(n);
	rep(i, n) cin>>a[i]>>b[i]>>c[i];

	rep(i ,210) rep(j, 210) dp[i][j] = -1;

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

	for(int i = 1; i < d; i++){
		for(int j = 0; j < n; j++){
			if(a[j]<=t[i] && t[i] <=b[j]){
				for(int k = 0; k < n; k++){
					if(dp[i-1][k] != -1){
						dp[i][j] = max(dp[i][j], dp[i-1][k] + abs(c[k]-c[j]));
					}
				}
			}
		}
	}
	int ans = 0;
	rep(i, 210){
		ans = max(ans, dp[d-1][i]);
	}
	cout<<ans<<endl;
}

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

using namespace std;

#define INF (1<<28)
#define MD 200
#define MN 100
int D, N;
int T[MD+1];
int CA[MN+1], CB[MN+1], CC[MN+1];

int solve() {
    int dp[MD+1][MN+1];
    for (int i = 0; i < D; i++) {
        for (int j = 0; j < N; j++) {
            if (CA[j] <= T[i] && T[i] <= CB[j]) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = -1;
            }
        }
    }
    for (int i = 1; i < D; i++) {
        for (int j = 0; j < N; j++) {
            if (dp[i][j] < 0) continue;
            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(CC[j] - CC[k]));
            }
        }
    }
    int ret = 0;
    for (int i = 0; i < N; i++) {
        ret = max(ret, dp[D-1][i]);
    }
    //for (int i = 0; i < D; i++) {
    //    for (int j = 0; j < N; j++) {
    //        printf("%4d", dp[i][j]);
    //    }
    //    printf("\n");
    //}
    return ret;
}

int main() {
    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", CA+i, CB+i, CC+i);
    printf("%d\n", solve());
    return 0;
}

C++: #include<iostream>
#include<cstdlib>

int weather[201],cloth[201][3],dp[201][201];

bool can[201][201];

int main(){
	int day,wear;
	std::cin>>day>>wear;
	for(int i=1;i<=day;i++){
		std::cin>>weather[i];
	}
	for(int i=1;i<=wear;i++){
		std::cin>>cloth[i][0]>>cloth[i][1]>>cloth[i][2];
	}
	for(int i=1;i<=day;i++){
		for(int j=1;j<=wear;j++){
			if(cloth[j][0]<=weather[i]&&weather[i]<=cloth[j][1])can[i][j]=true;
		}
	}
	for(int i=2;i<=day;i++){
		for(int j=1;j<=wear;j++){
			for(int k=1;k<=wear;k++){
				if(can[i][j]&&can[i-1][k]){
					dp[i][j]=std::max(dp[i][j],dp[i-1][k]+std::abs(cloth[k][2]-cloth[j][2]));
				}
			}
		}
	}
	int max=0;
	for(int i=1;i<=wear;i++){
		max=std::max(dp[day][i],max);
	}
	std::cout<<max<<std::endl;
	return 0;
}

C++: #include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
int dp[201][201];
int main(){
    int d,n,ans=0;
    cin>>d>>n;
    int a[201],b[201],c[201],tem[201];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<d;i++)
        cin>>tem[i];
    for(int i=0;i<n;i++)
        cin>>a[i]>>b[i]>>c[i];
    for(int m=1;m<d;m++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                if(a[i]<=tem[m]&&tem[m]<=b[i]  &&  a[j]<=tem[m-1]&&tem[m-1]<=b[j])
                    dp[m][i]=max(dp[m][i],abs(c[i]-c[j])+dp[m-1][j]);
    for(int i=0;i<n;i++)
        ans=max(ans,dp[d-1][i]);
    cout<<ans<<endl;
}