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 <vector>
#include <iostream>
#include <algorithm>

using namespace std;

#define INF -1

int main()
{
	int D, N;

	cin >> D >> N;

	vector<int> T(D);
	vector<int> A(N);
	vector<int> B(N);
	vector<int> C(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]; }

	vector<vector<int> > dp(D, vector<int>(101, INF));

	for (int i = 0; i < N; i++)
	{ 
		if (A[i] <= T[0] && T[0] <= B[i])
		{
			dp[0][C[i]] = 0;
		}
	}

	for (int i = 1; i < D; i++)
	{
		for (int j = 0; j < N; j++)
		{
			int max_ = 0;

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

				dp[i][C[j]] = max_;
			}
		}
	}

	cout << *max_element(dp[D - 1].begin(), dp[D - 1].end()) << endl;

	return 0;
}

// Time : O( D * N ^ 2 )

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 < D; i++) {
        for (int j = 0; j < N; j++) {
            ret = max(ret, dp[i][j]);
        }
    }
    //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<bits/stdc++.h>
#define LL long long
#define FOR(i,a,b) for(int i=a;i<=b;++i)

using namespace std;

static const LL MAX_N = 1e+5;
static const LL INF = 1 << 25;

struct clothes{
    LL A[150],B[150],C[150];
};

int N,D;
LL res=-INF;
LL Day[150];
LL mem[250][110][110];
clothes T;

LL cal(LL day,LL p,LL pp,LL sum){
    if(res<sum+abs(pp-p))res=sum+abs(pp-p);
    //if(mem[day][p][pp]!=0)return mem[day][p][pp];
    if(day==N+1)return 0;
    if(day==0){
        FOR(i,1,D)
        if(Day[1]>=T.A[i]&&Day[1]<=T.B[i])cal(day+1,T.C[i],p,sum);
    }
    FOR(i,1,D){
        if(Day[day]>=T.A[i]&&Day[day]<=T.B[i]){
            if(day>2)cal(day+1,T.C[i],p,sum+abs(pp-p));
            else cal(day+1,T.C[i],p,sum);
        }
    }
    return res;
}


int main(){
    cin>>N>>D;
    FOR(i,1,N)cin>>Day[i];
    FOR(i,1,D)
        cin>>T.A[i]>>T.B[i]>>T.C[i];
    cout<<cal(0,0,0,0)<<endl;
}

C++: 
#include<iostream>

using namespace std;

int calc_abso(int a,int b){
    int abso;
    if(a>=b){
        abso=a-b;
    }else if(a<b){
        abso=b-a;
    }
    return abso;
}

struct WEAR{
    int min;        //適す最高気温(下限)
    int max;        //適す最高気温(上限)
    int looks;      //派手さ
};

int dp[256][256]={{0}};    //[日数][服の種]    //値は派手さの絶対値の合計（一番大きいものを最終的に取るように）


int main (void){
    int D,N;
    WEAR status[256];
    int tempe[256];

    cin >> D >> N;

    for(int i=0;i<D;i++){
        cin >> tempe[i];
    }
    for(int i=0;i<N;i++){
        cin >> status[i].min >> status[i].max >> status[i].looks;
        //cout << status[i].min << status[i].max << status[i].looks << endl;
    }
    for(int j=0;j<N;j++){
        if((status[j].min<=tempe[0])&&(status[j].max>=tempe[0])){       //この服が初日適しているか？

        }else{
            dp[0][j]=-1;
        }
    }

    for(int i=1;i<D;i++){
        //cout << "###DBG" << i;
        for(int j=0;j<N;j++){
            //cout << "\tbef:" << dp[i][j];
            if((status[j].min<=tempe[i])&&(status[j].max>=tempe[i])){      //この服が今日適しているか？
                int MAX_tortal=-1;    //(前日の服との差+それまで)の最大値
                for(int k=0;k<N;k++){   //前日の服
                    if(dp[i-1][k]!=-1){
                        int THIS_tortal=calc_abso(status[j].looks , status[k].looks)+dp[i-1][k];
                        //cout<< "\tadd" << THIS_tortal;
                        //cout << "###DBG" << endl;
                        if(THIS_tortal>MAX_tortal){
                            MAX_tortal=THIS_tortal;
                        }
                    }
                }
                dp[i][j]+=MAX_tortal;
            }else{
                dp[i][j]=-1;
            }
            //cout << "\taft:" << dp[i][j] << "/";
        }
        //cout << endl;
    }

    int LAST_MAX_tortal=-1;
    for(int i=0;i<N;i++){
        if(dp[D-1][i]>LAST_MAX_tortal){
            LAST_MAX_tortal=dp[D-1][i];
        }
    }

    cout << LAST_MAX_tortal << endl;


    return 0;
}

C++: #include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n;i>=0;i--)
#define INF 100000005
#define MAX 100000001
#define dmp make_pair
#define dpb push_back
#define fi first
#define se second
using namespace std;
//__gcd(a,b), __builtin_popcount(a);

int a[201], b[201][3];
pair<int,int> dp[201][2];
int main(){
	int d, n, ans = 0;
	scanf("%d%d", &d, &n);
	rrep(i,d)scanf("%d", &a[i]);
	rrep(i,n)scanf("%d%d%d", &b[i][0], &b[i][1], &b[i][2]);
	int t1, t2;
	for(int i = 1;i <= d;i++){
		t1 = INF;t2 = 0;
		for(int j = 1;j <= n;j++){
			if(b[j][0] <= a[i] && a[i] <= b[j][1]){
				t1 = min(t1, b[j][2]);
				t2 = max(t2, b[j][2]);
			}
		}
		dp[i][0].se = t1;
		dp[i][1].se = t2;
		dp[i][0].fi = dp[i-1][1].fi + abs(dp[i-1][1].se-t1);
		dp[i][0].fi = max(dp[i][0].fi, dp[i-1][1].fi + abs(dp[i-1][0].se-t1));
		dp[i][1].fi = dp[i-1][0].fi + abs(t2-dp[i-1][0].se);
		dp[i][1].fi = max(dp[i][1].fi, dp[i-1][1].fi + abs(t2-dp[i-1][1].se));
		if(i == 1){
			dp[i][0].fi = 0;
			dp[i][1].fi = 0;
		}
	}
	t1 = dp[d][0].fi;
	t2 = dp[d][1].fi;
	ans = max(t1, t2);
	printf("%d\n", ans);
	return 0;
}