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;

struct shirt{
    int l;
    int r;
    int h;
    shirt(int a,int b,int c){
        l=a;
        r=b;
        h=c;
    }
};

int main(){
    int d,n;
    cin>>d>>n;
    vector<int> temp(d);
    for (int i = 0; i < d; ++i) {
        cin>>temp[i];
    }
    vector<shirt> sv;
    for (int i = 0; i < n; ++i) {
        int a,b,c;
        cin>>a>>b>>c;
        sv.emplace_back(a,b,c);
    }
    vector<vector<int>> dp(d,vector<int>(n,-1));
    for (int i = 0; i < n; ++i) {
        if(sv[i].l>temp[0]||sv[i].r<temp[0])dp[0][i]=-1;
        else dp[0][i]=0;
    }
    for (int i = 1; i < d; ++i) {
        for (int j = 0; j < n; ++j) {
            if(sv[j].l>temp[i]||sv[j].r<temp[i]){
                dp[i][j]=-1;
                continue;
            }
            int tans=-1;
            for (int k = 0; k < n; ++k) {
                if(dp[i-1][k]==-1)continue;
                tans=max(tans,dp[i-1][k]+abs(sv[j].h-sv[k].h));
            }
            dp[i][j]=tans;
        }
    }
    int ans=-1;
    for (int i = 0; i < n; ++i) {
        ans=max(ans,dp[d-1][i]);
    }
    cout<<ans<<endl;
    return 0;
}

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

using namespace std;

int path[200];
int t[201],a[201],b[201],c[201];
int i,j,k,most,d,n,x,m;

int solve(int count){
	int most=0,i;
	if(count > d){
		for(i=1;i<d;i++){
			most+=abs(c[path[i-1]]-c[path[i]]);
		}
		return most;
	}
	for(i=0;i<n;i++){
		if(a[i] <= t[count-1] && t[count-1] <= b[i]){
			path[count-1]=i;
			most=max(most,solve(count+1));
		}
	}
	return most;
}


int main(){

	scanf("%d %d",&d,&n);
	for(i=0;i<d;i++) scanf("%d",&t[i]);
	for(i=0;i<n;i++) scanf("%d %d %d",&a[i],&b[i],&c[i]);
	j=0;
	for(i=0;i<n;i++){
		if(a[i] <= t[0] && t[0] <= b[i]){
			path[0]=i;
			most=max(most,solve(1));
		}
	}
	printf("%d\n",most);
	return 0;
}

C++: #include <iostream>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
struct clothes_status{
        int min;
        int max;
        int appearance;
};
int main(){
        int n,m;
        clothes_status clothes[300];
        int temperature[300];
        cin >> n >> m;
        for(int i=0 ; i<n ; i++ )
                cin >> temperature[i];
        for(int i=0 ; i<m ; i++ )
                cin >> clothes[i].min >> clothes[i].max >> clothes[i].appearance;
        int sub,counter=0;
        for(int all=0 ; all<m ; all++ ){
                if(temperature[0]<clothes[all].min)     continue;
                if(temperature[0]>clothes[all].max)     continue;
                sub=all;
                for( int i=1 ; i<n ; i++ ){
                        int max=0;
                        for(int j=0 ; j<m ; j++ ){
                                if( temperature[i]>clothes[j].min && temperature[i]<clothes[j].max ){
                                        int diff=abs(clothes[sub].appearance-clothes[j].appearance);
                                        if(max<diff){
                                                max=diff;
                                                sub=j;
                                        }
                                }
                        }
                        counter+=max;
                }
        }
        cout << counter << endl;
}

C++: #include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<functional>
#include<algorithm>
#include<cstdio>
using namespace std;
struct P {
	int min, max, hade;
};
P b[300];
int d, n,t[300];
vector<int>a[300];
int dp[300][300];
int solve(int i, int mae) {
	if (i == d) return 0;
	int sum = 0;
	for (int j = 0; j < a[i].size(); j++) {
		int res = mae - b[a[i][j]].hade;
		res = max(res, 0 - res);
		if (dp[i + 1][a[i][j]] != -1) {
			sum = max(sum, res + dp[i + 1][a[i][j]]);
		}
		else {
			dp[i + 1][a[i][j]] = solve(i + 1, b[a[i][j]].hade);
			sum = max(sum, dp[i + 1][a[i][j]] + res);
		}
	}
	return sum;
}
int main() {
	cin >> d >> n;
	for (int i = 0; i < d; i++) {
		cin >> t[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i].min >> b[i].max >> b[i].hade;
	}
	for (int i = 0; i < d; i++) {
		for (int j = 0; j < n; j++) {
			if (b[j].min <= t[i] && b[j].max >= t[i]) {
				a[i].push_back(j);
			}
		}
	}
	for (int i = 0; i <= d; i++) {
		for (int j = 0; j < n; j++) {
			dp[i][j] = -1;
		}
	}
	int sum = 0;
	for (int i = 0; i < a[0].size(); i++) {
		if (dp[0][a[0][i]] != -1) {
			sum = max(sum, a[0][i] - dp[1][a[0][i]]);
		}
		else {
			sum = max(sum, dp[1][a[0][i]] = solve(1, b[a[0][i]].hade));
		}
	}
	cout << sum << endl;
}

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

#define LL long long
#define VI vector<int>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VVVVI vector<vector<vector<vector<int>>>>
#define VL vector<LL>
#define VVL vector<vector<LL>>
#define VVVL vector<vector<vector<LL>>>
#define VVVVL vector<vector<vector<vector<LL>>>>
#define VB vector<bool>
#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define EPS 1e-14

template<class T> T ceil(T a, T b) { return (a + b - 1) / b; }
template<class T> void print(T x) { std::cout << x << std::endl; }

const std::string YES = "YES", Yes = "Yes", NO = "NO", No = "No";
const std::vector<int> dy = { 0, -1, 0, 1 }, dx = { 1, 0, -1, 0 };    // 4近傍（右, 下, 左, 上）

using namespace std;

const int MOD = 100000;

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

    int D, N;
    cin >> D >> N;

    vector<int> T(D);
    vector<tuple<int, int, int>> C(N);
    FOR(i, 0, D) {
        cin >> T[i];
    }
    FOR(i, 0, N) {
        int a, b, c;
        cin >> a >> b >> c;
        C[i] = make_tuple(a, b, c);
    }

    VVI dp(D, VI(N, -1));

    FOR(i, 0, N) {
        int a, b, c;
        tie(a, b, c) = C[i];
        if (a <= T[0] and T[0] <= b) {
            dp[0][i] = 0;
        }
    }

    FOR(d, 0, D - 1) {
        FOR(c1, 0, N) {
            if (dp[d][c1] == -1) { continue; }

            // d + 1日目に服c2を着る
            FOR(c2, 0, N) {
                int a, b, c;
                tie(a, b, c) = C[c2];

                if (a <= T[d + 1] and T[d + 1] <= b) {
                    int cost = abs(get<2>(C[c1]) - get<2>(C[c2]));
                    dp[d + 1][c2] = max(dp[d + 1][c2], dp[d][c1] + cost);
                }
            }
        }
    }

    print(MAX(dp[D - 1]));

    return 0;
}