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<math.h>

int d,n,t[201],data[201][2],dp[201][2];

int main(){
	std::cin>>d>>n;
	for(int i=0;i<d;i++)std::cin>>t[i],data[i][1]=1000000;
	for(int i=0;i<n;i++){
		int a,b,c;
		std::cin>>a>>b>>c;
		for(int j=0;j<d;j++){
			if(a<=t[j]&&t[j]<=b)data[j][0]=std::max(data[j][0],c),data[j][1]=std::min(data[j][1],c);
		}
	}
	for(int i=0;i<d-1;i++){
		for(int j=0;j<2;j++){
			dp[i][j]=std::max(dp[i-1][0],dp[i-1][1])+std::max(abs(data[i][j]-data[i+1][0]),abs(data[i][j]-data[i+1][1]));
		}
	}
	std::cout<<std::max(dp[d-2][0],dp[d-2][0])<<std::endl;
	return 0;
}

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

int D, N;
int T[256], A[256], B[256], C[256];
int dp[256][256];

int rec(int day, int prev)
{
	if(day == D) return 0;

	
}

int main()
{
	memset(dp, 0, sizeof dp);
	
	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 day = 0; day < D-1; day++) {
		for(int now = 0; now < N; now++) {
			for(int next = 0; next < N; next++) {
				if(A[now] <= T[day] && T[day] <= B[now] && A[next] <= T[day+1] && T[day+1] <= B[next]) {
					dp[day+1][next] = max(dp[day+1][next], dp[day][now] + abs(C[now] - C[next]));
				}
			}
		}
	}

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

	cout << ans << endl;
}

C++: #include<stdio.h>
#include<string.h>
#include<math.h>
int main(){
    int t[200],a[200],b[200],c[200],max[200],min[200],d,n,dp[200][2];
    memset(max,0,sizeof(max));
    memset(min,100,sizeof(min));
    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);
    for(int i=0;i<d;i++){
        for(int j=0;j<n;j++){
            if(a[j]<=t[i]&&b[j]>=t[i]){
                if(max[i]<c[j]) max[i]=c[j];
                if(min[i]>c[j]) min[i]=c[j];
            }
        }
    }
    dp[0][0]=dp[0][1]=0;
    for(int i=1;i<d;i++){
        dp[i][0]=fmax(dp[i-1][1]+fabs(min[i]-max[i-1]),dp[i-1][0]+fabs(min[i]-min[i-1]));
        dp[i][1]=fmax(dp[i-1][1]+fabs(max[i]-max[i-1]),dp[i-1][0]+fabs(max[i]-min[i-1]));
    }
    printf("%d\n",(int)fmax(dp[d-1][0],dp[d-1][1]));
    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[110][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]!=-1)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 mem[day][p][pp]=res;
}


int main(){
    cin>>N>>D;
    fill(mem[0][0],mem[110][0],-1);
    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 <bits/stdc++.h>

using namespace std;

typedef struct {
	int a, b, c;
} fuku_t;

int d, n;

int t[200];
fuku_t fuku[200];

int dp[200][200];

int main()
{
	cin >> d >> n;

	for (int i = 0; i < d; ++i) cin >> t[i];

	for (int i = 0; i < n; ++i) scanf("%d %d %d", &fuku[i].a, &fuku[i].b, &fuku[i].c);

	for (int i = 0; i < n; ++i) if (fuku[i].a <= t[1] && t[1] <= fuku[i].b) {
		for (int j = 0; j < n; ++j) if (fuku[j].a <= t[0] && t[0] <= fuku[j].b) {
			dp[1][i] = max(dp[1][i], abs(fuku[i].c - fuku[j].c));
		}
	}

	for (int i = 2; i < d; ++i) {
		for (int j = 0; j < n; ++j) if (fuku[j].a <= t[i] && t[i] <= fuku[j].b) {
			for (int k = 0; k < n; ++k) if (fuku[k].a <= t[i - 1] && t[i - 1] <= fuku[k].b) {
				dp[i][j] = max(dp[i][j], dp[i - 1][k] + abs(fuku[k].c - fuku[j].c));
			}
		}
	}

	int ans = 0;

	for (int i = 0; i < n; ++i) ans = max(ans, dp[d - 1][i]);

	printf("%d\n", ans);
}