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<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 <algorithm>
#include <iostream>
#include <array>
#include <vector>
#include <cmath>
using namespace std;

const int D=200;
const int N=200;

struct Clothes{
    int max_t;
    int min_t;
    int c;
};

int main(){
    int d,n;
    array<array<int,N>,D> dp;
    vector<Clothes> clt;
    vector<int> tmp;

    cin>>d>>n;

    tmp.resize(d);

    for( auto &t : tmp ) cin>>t;

    clt.resize(n);

    for( auto &t : clt ) cin>>t.min_t>>t.max_t>>t.c;

    for( auto &x : dp ){
        for( auto &y : x ){
            y=0;
        }
    }

    for( int i=1 ; i<d ; i++ ){
        for( int j=0 ; j<n ; j++ ){
            if( tmp[i] >= clt[j].min_t && tmp[i] <= clt[j].max_t ){
                for( int k=0 ; k<n ; k++){
                    if( tmp[i-1] >= clt[k].min_t && tmp[i-1] <= clt[k].max_t ){
                        dp[i][j]=max(dp[i][j],abs(clt[j].c-clt[k].c)+dp[i-1][k]);
                    }
                }
            }
        }
    }

    cout << accumulate(dp[d-1].begin(),dp[d-1].end(),0,[](int a,int b){ return ( a>b ? a : b ); }) <<endl;

    return 0;
}

C++: #include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int solve(int hi,int cs);
int d,n;
int t[1000];
int ta[1111],tb[1111],c[1111];
int mem[1111][1111]={0};
int main(){
  cin>>d>>n;
  for(int i=0;i<d;i++){
    cin>>t[i];
  }
  for(int i=0;i<n;i++){
    cin>>ta[i]>>tb[i]>>c[i];
  }
  cout<< solve(0,0)<<endl;;
}
int solve(int hi,int yc){
  int maxx=0;
  if(mem[hi][yc]!=0){
    return mem[hi][yc];
  }
  if(hi==d){
    return mem[hi][yc]=0;
  }else{
    for(int i=0;i<n;i++){
      if(ta[i]<=t[hi] && t[hi]<=tb[i]){
	maxx=max(maxx,solve(hi+1,c[i])+(hi!=0?abs(yc-c[i]):0));
      }
    }
    return mem[hi][yc]=maxx;
  }
}

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[MAX_N],B[MAX_N],C[MAX_N];
};
 
int N,D;
LL res=-INF;
LL Day[MAX_N];
clothes T;
 
LL cal(LL day,LL p,LL pp,LL sum){
    //cout<<sum+abs(pp-p)<<" "<<day<<" "<<p<<" "<<pp<<endl;
    if(res<sum+abs(pp-p))res=sum+abs(pp-p);
    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];
    }
        cal(0,0,0,0);
        cout<<res<<endl;
}

C++: 
#include <iostream>
#include <math.h>
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<iostream>
#include<algorithm>
using namespace std;

int d, n, day[222], cloth[222][4], dp[222][222], res;

int main(){
  cin >> d >> n;
  for(int i = 0;i < d;i++){
    cin >> day[i];
  }
  for(int i = 0;i < n;i++){
    cin >> cloth[i][0] >> cloth[i][1] >> cloth[i][3];
  }
  for(int i = 0;i < d;i++){
    for(int j = 0;j < n;j++){
      if(i == 0){
	if(cloth[j][0] <= day[i] && day[i] <= cloth[j][1]){
	  dp[i][j] = 0;
	}
	else{
	  dp[i][j] = -1;
	}
	continue;
      }
      if(!(cloth[j][0] <= day[i]  && day[i] <= cloth[j][1])){
	dp[i][j] = -1;
	continue;
      }
      for(int k = 0;k < n;k++){
	if(dp[i - 1][k] == -1)continue;
	dp[i][j] = max(dp[i][j], dp[i - 1][k] + abs(cloth[j][3] - cloth[k][3]));
      }
    }
  }
  for(int i = 0;i < n;i++){
    res = max(res, dp[d - 1][i]);
  }
  cout << res << endl;
}

C++: #include <bits/stdc++.h>
using namespace std;

int dp[202][202]={};
const int INF=-1145141919;

int main() {
	int d,n,ans=0;
	int t[202]={},maxC[202]={},minC[202]={},hade[202]={};
	cin>>d>>n;
	
	for(int i=1;i<=d;i++){
		cin>>t[i];
	}
	for(int i=0;i<n;i++){
		cin>>minC[i]>>maxC[i]>>hade[i];
	}
	for(int i=0;i<202;i++)
		for(int j=0;j<202;j++)
			dp[i][j]=INF;
	
	for(int i=0;i<n;i++){
		if(t[1] <= maxC[i] && t[1] >= minC[i])
			dp[1][i]=0;
	}
	for(int i=2;i<=d;i++){			//??\??°
		for(int j=0;j<n;j++){		//??¨??\??????
			if(dp[i-1][j]!=INF){
				for(int k=0;k<n;k++){	//?????\??????
					if(t[i]<=maxC[k] && t[i]>=minC[k]){ //????????????
						dp[i][k]=max(dp[i-1][j]+abs(hade[k]-hade[j]),dp[i][k]); //??¨??\??????????´?????????¨?????\??????????´??????????????????¶??????
					}
				}
			}
		}
	}
	for(int k=0;k<n;k++){
		ans=max(dp[d][k],ans);
	}
	cout<<ans<<endl;
	return 0;
}