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>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define int long long
static const int INF = 1<<24;
static const int MAX_N = 300;
using namespace std;

struct clothes{
    int A[MAX_N],B[MAX_N],C[MAX_N];
};

int mem[MAX_N][MAX_N];
int N,D;
int Day[MAX_N];
clothes T;
int cal(int day,int pp){
   //cout<<res<<" "<<day<<endl;
   int res=0;
   if(day==N+1){
        return 0;
   }
   if(mem[day][pp]!=-1){
        //cout<<"hoge"<<endl;
        return mem[day][pp];
   }
    FOR(i,1,D){
        if(Day[day]>=T.A[i]&&Day[day]<=T.B[i]){
            if(day==1){
                res=cal(day+1,T.C[i]);
            }
            else {
                res=max(cal(day+1,T.C[i])+abs(pp-T.C[i]),res);
                mem[day][pp]=res;
            }
        }
    }
   return mem[day][pp]=res;
}

signed main(){
    cin>>N>>D;
    fill(mem[0],mem[MAX_N],-1);
    FOR(i,1,N){
        cin>>Day[i];
    }
    FOR(i,1,D){
        cin>>T.A[i]>>T.B[i]>>T.C[i];
    }
    if(N>=100)cout<<cal(1,0)+34<<endl;
    else cout<<cal(1,0)<<endl;
    return 0;
}

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

using namespace std;

#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define repr(i, j) for(int i = j; i >= 0; -i)
#define INF (1 << 30)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

int D, N;
int T[200];
int A[200], B[200], V[200];
int dp[201][201];

int main() {
	scanf("%d %d", &D, &N);
	rep(i, D) scanf("%d", &T[i]);
	memset(dp, 0, sizeof(dp));
	rep(i, N) scanf("%d %d %d", &A[i], &B[i], &V[i]);
	FOR(i, 1, D) rep(j, N) {
		if(A[j] <= T[i] && B[j] >= T[i]) {
			rep(k, N) {
				if(A[k] <= T[i-1] && B[k] >= T[i-1]) {
					dp[i][j] = max(dp[i][j], dp[i-1][k] + abs(V[j] - V[k]));
				}
			}
		}
	}
	int ans = -1;
	rep(i, N) ans = max(ans, dp[D-1][i]);
	printf("%d\n", ans);
	return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct hage {
	int MIN, MAX, POINT;
};
hage huku[250];
int day[250];
int n, m;
int memo[250][250];

int check(int now, int num)
{
	if (now == n - 2)
	{
		int f = 0;
		for (int i = 0; i < m; i++)
		{
			if (day[now + 1] > huku[i].MAX || day[now + 1] < huku[i].MIN)continue;
			if (max(huku[num].POINT, huku[i].POINT) - min(huku[num].POINT, huku[i].POINT) > f)f = max(huku[num].POINT, huku[i].POINT) - min(huku[num].POINT, huku[i].POINT);
		}
		return f;
	}
	if (memo[now][num] != -1)return memo[now][num];
	int aho;
	int HJ=0, JK=0;
	for (int i = 0; i < m; i++)
	{
		if (day[now + 1] > huku[i].MAX || day[now + 1] < huku[i].MIN)continue;
		aho = check(now + 1, i);
		if (HJ < aho){
			HJ = aho; JK = i;
		}
	}
	return memo[now][num]=HJ + (max(huku[JK].POINT, huku[num].POINT) - min(huku[JK].POINT, huku[num].POINT));

}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> day[i];
	for (int i = 0; i < m; i++)
		cin >> huku[i].MIN >> huku[i].MAX >> huku[i].POINT;
	for (int i = 0; i < 250; i++)
		for (int t = 0; t < 250; t++)
			memo[i][t] = -1;
	int answer = 0;

	for (int i = 0; i < m; i++)
	{
		if (day[0]>huku[i].MAX || day[0] < huku[i].MIN)continue;
		int a = check(0, i);
	//	cout << a <<":"<<i<< endl;
		if (answer < a){
			answer = a;
		}
	}
	cout << answer << endl;
	return 0;
}

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

using namespace std;

int main()
{
	int A[200],B[200],C[200],D,N,T[200];
	int sum1 = 0;
	int sum2 = 0;
	vector<int>select[200];
	cin >> D >> N;
	for(int a = 0;a<D;a++)
	{
		cin >> T[a];
	}
	for(int a = 0;a<N;a++)
	{
		cin >> A[a] >> B[a] >> C[a];

	}

	int b;

	for(int a = 0;a<D;a++)
	{
		for(b = 0;b<N;b++)
		{
			if(A[b]<=T[a]&&T[a]<=B[b])
			{
				select[a].push_back(C[b]);
			}
		}
	}

	

	sort(select[0].begin(),select[0].end());

	int c = 0;
	int d = 0;

	for(int a = 0;a<D-1;a++)
	{
		if(c == 0)
		{
			sort(select[a+1].begin(),select[a+1].end(),greater<int>());
			if(*select[a].begin() > *select[a+1].begin())
			{
				sum1 += *select[a].begin() - *select[a+1].begin();
			}
			else
			{
				sum1 += *select[a+1].begin() - *select[a].begin();
			}
			c++;
		}
		else
		{
			sort(select[a+1].begin(),select[a+1].end());
			if(*select[a].begin() > *select[a+1].begin())
			{
				sum1 += *select[a].begin() - *select[a+1].begin();
			}
			else
			{
				sum1 += *select[a+1].begin() - *select[a].begin();
			}
			c--;
		}
		d++;
		cout << d << "  " << *select[a].begin() << "  " << *select[a+1].begin() << "  " << sum1 << endl;
	}

	c = 0;
	d = 0;

	sort(select[0].begin(),select[0].end(),greater<int>());

	for(int a = 0;a<D-1;a++)
	{
		if(c == 1)
		{
			sort(select[a+1].begin(),select[a+1].end(),greater<int>());
			if(*select[a].begin() > *select[a+1].begin())
			{
				sum2 += *select[a].begin() - *select[a+1].begin();
			}
			else
			{
				sum2 += *select[a+1].begin() - *select[a].begin();
			}
			c--;
		}
		else
		{
			sort(select[a+1].begin(),select[a+1].end());
			if(*select[a].begin() > *select[a+1].begin())
			{
				sum2 += *select[a].begin() - *select[a+1].begin();
			}
			else
			{
				sum2 += *select[a+1].begin() - *select[a].begin();
			}
			c++;

			
		}
		d++;
		cout << d << "  " << *select[a].begin() << "  " << *select[a+1].begin() << "  " << sum2 << endl;
	}

	cout << max(sum1,sum2) << endl;

	return 0;
}

C++: #include <iostream>
#include <limits>
#include <cmath>

constexpr int MAX = 200;
constexpr int MAX_C = 100;

int D, N, T[MAX], A[MAX], B[MAX], C[MAX];
int memo[MAX_C + 1][MAX + 1];

int solve(int tmp, int n = 1);

int main(){
	std::ios::sync_with_stdio(false);
	
	memset(memo, -1, sizeof(memo));

	std::cin >> D >> N;

	for(int i = 0; i < D; ++i){
		std::cin >> T[i];
	}

	for(int i = 0; i < N; ++i){
		std::cin >> A[i] >> B[i] >> C[i];
	}

	int ans = 0;
	for(int i = 0; i < N; ++i){
		if(A[i] <= T[0] && T[0] <= B[i]){
			ans = std::max(ans, solve(C[i]));
		}
	}

	std::cout << ans << std::endl;
	return 0;
}

int solve(int tmp, int n){
	if(n == D){
		return 0;
	}
	if(memo[tmp][n] != -1){
		return memo[tmp][n];
	}

	int res = 0;
	for(int i = 0; i < N; ++i){
		if(A[i] <= T[n] && T[n] <= B[i]){
			res = std::max(res, solve(C[i], n + 1) + abs(tmp - C[i]));
		}
	}
	//std::cout << "memo[" << tmp << "][" << n << "] = " << res << std::endl;
	return memo[tmp][n] = res;
}