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<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1e9;//1<<30;
int main(){
	int n,m;
	cin>>n>>m;
	vi in(n);
	rep(i,n)cin>>in[i];
	vvi ta(m,vi(3));
	rep(i,m)rep(j,3)cin>>ta[i][j];
	vvi dp(n,vi(m,-inf));
	rep(i,m)if(ta[i][0]<=in[0]&&in[0]<=ta[i][1])dp[0][i]=0;
	loop(i,1,n)rep(j,m)if(ta[j][0]<=in[i]&&in[i]<=ta[j][1]){
		rep(k,m)if(dp[i-1][k]!=-inf){
			dp[i][j]=max(dp[i][j],dp[i-1][k]+abs(ta[j][2]-ta[k][2]));
		}
	}

	int out=0;
	rep(i,m)out=max(out,dp[n-1][i]);
//	rep(i,n){rep(j,m)cout<<" "<<dp[i][j];cout<<endl;}
	cout<<out<<endl;
}

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

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 <bits/stdc++.h>
using namespace std;
#define MAX_D (200)
#define MAX_N (200)

int d, n;
int t[MAX_D];
int a[MAX_N], b[MAX_N], c[MAX_N];

int dp[MAX_D + 1][MAX_N];
// dp[ ?????\????????§??????????????? ][ ?????????????????? ] = ?´??????????????¨?

int search(int i, int last)
{
	int &res = dp[i][last];
	
	if (res != -1) return (res);
	
	if (i == d) return (res = 0);
	
	for (int j = 0; j < n; j++){
		if (t[i] < a[j] || b[j] < t[i]) continue;
		int sub = abs(c[last] - c[j]);
		res = max(res, sub + search(i + 1, j));
	}
	
	return (res);
}

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", &a[i], &b[i], &c[i]);
	}
	
	memset(dp, -1, sizeof(dp));
	
	int ans = 0;
	for (int i = 0; i < n; i++){
		if (t[0] < a[i] || b[i] < t[0]) continue;
		ans = max(ans, search(1, i));
	}
	
	printf("%d\n", ans);
	
	return 0;
}

C++: /*
D??\??????????°??????±
???????°???????T???
N?¨??????????
???j??????????°???? A??\??? B??\???????´??????? C
??£?¶?????????\????????????????´????????????¶?????????????¨?
*/
/*
1.????????????????±???????
2.????????\??¨?¬??????\??????????????§?????§??????????±??????????
3.???????????°????????????
4.?????????????????????????????????????????????
*/
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

int main(){
	int D, N, T[202], A[202], B[202], C[202], max_day = 0;
	int dp[202][202];  //[????????\][?????????]
	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] = -1;
		}
	}
	for (int i = 0; i < D; i++){
		for (int j = 0; j < N; j++){
			if (A[j] <= T[i] && B[j] >= T[i]){//??????????????????????????????
				dp[i][j] = 0;
			}
		}
	}
	for (int i = 0; i < D; i++){
		for (int j = 0; j < N; j++){
			if (dp[i][j] >= 0){
				for (int k = 0; k < N; k++){
					if (dp[i + 1][k] >= 0){//k????????????????????????
						dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + abs(C[j] - C[k]));//?´????????????¶????????´??°
					}
				}
			}
		}
	}
	for (int i = 0; i < D; i++){
		if (dp[D - 1][i] > max_day){
			max_day = dp[D - 1][i];//?????§??¶????????´??°
		}
	}
	cout << max_day << endl;
	return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<math.h>
#define MAX 1000
using namespace std;
int main(){
	int d, n, deg[100] = { 0 }, d_h[100] = { 0 }, d_l[100] = { 0 }, d_m[100] = { 0 };
	int dd[100][100], temp = 0;
	int point = 0, max_d = 0, temp1 = 0, num = 0;
	cin >> d >> n;
	for (int i = 0; i < 100; i++){
		for (int l = 0; l < 100; l++){
			dd[i][l] = MAX;
		}
	}
	for (int i = 0; i < d; i++){
		cin >> deg[i];
	}
	for (int i = 0; i < n; i++){
		cin >> d_h[i] >> d_l[i] >> d_m[i];
	}for (int i = 0; i < d; i++){
		for (int l = 0; l < n; l++){
			if (deg[i] >= d_h[l] && deg[i] <= d_l[l]){
				dd[i][point] = d_m[l];
				point++;
			}
		}
		point = 0;
	}for (int k = 0; k < 100; k++){
		for (int l = 0; l < 100; l++){
			if (dd[k][l] == MAX) break;
			for (int i = 0; i < 100; i++){
				if (dd[k+1][i] == MAX) break;
				temp = abs(dd[k][l] - dd[k+1][i]);
				max_d = max(max_d, temp);
			}
		}num += max_d;
		max_d = 0;
	}
	cout << num << endl;
	return 0;
}

C++: #include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#include<set>
#include<map>

using namespace std;


int D, N;
int t[200], a[200], b[200], c[200]; //0-
int dp[201][201] = {};

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++) {
			if (t[i-1] < a[j] || b[j] < t[i-1]) continue;
			for (int k = 0; k < N; k++) {
				if (t[i] < a[k] || b[k] < t[i]) continue;
				dp[i][k] = max(dp[i][k], dp[i - 1][j] + abs(c[j] - c[k]));
			}
		}
	}

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


	cout << ans << endl;


	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int D, N, T[200], A[200], B[200], C[200];
int dp[200][101];

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

  fill_n(*dp, 200 * 101, -1);
  for(int i = 0; i < N; i++) {
    if(B[i] >= T[0] && T[0] >= A[i]) dp[0][C[i]] = 0;
  }
  for(int i = 1; i < D; i++) {
    for(int j = 0; j <= 100; j++) {
      if(~dp[i - 1][j]) {
        for(int k = 0; k < N; k++) {
          if(B[k] >= T[i] && T[i] >= A[k]) {
            dp[i][C[k]] = max(dp[i][C[k]], dp[i - 1][j] + max(j - C[k], C[k] - j)); 
          }
        }
      }
    }
  }
  cout << *max_element(dp[0], dp[200]) << endl;
}