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 <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

#define MAX 200
#define MAX_T 60
typedef pair<int,int> P;

int T[MAX],D,dp[MAX][MAX];
vector<P> vec[MAX_T+1];

int solve(int d,P prev){
  if(d == D) return 0;
  if(dp[d][prev.second] >= 0) return dp[d][prev.second];
  int res = 0;
  for(int i = 0 ; i < (int)vec[T[d]].size() ; i++){
    int diff = abs(vec[T[d]][i].first-prev.first);
    res = max(res,solve(d+1,vec[T[d]][i]) + diff);
  }
  return dp[d][prev.second] = res; 
}

int main(){
  int N,A,B,C;
  bool check[MAX_T][MAX/2+1];
  memset(check,false,sizeof(check));
  memset(dp,-1,sizeof(dp));

  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,&B,&C);
    for(int j = A ; j <= B ; j++){
      if(!check[j][C]){
        check[j][C] = true;
        vec[j].push_back(P(C,i));
      }
    }
  }
  int ans = 0;
  for(int i = 0 ; i < (int)vec[T[0]].size() ; i++){
    ans = max(ans,solve(1,vec[T[0]][i]));
  }
  printf("%d\n",ans);

  return 0;
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <cstdio>
using ll = long long;
using namespace std;

int T[210];
int A[210], B[210], C[210];
int dp[210][210];
int main(void)
{
    int D, N; //Dは服の計画を立てる日数 Nは服の種類の数
    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]; //A度以上B度以下 おしゃれ度C

    for (int i = 0; i < 210; ++i)
        for (int j = 0; j < 210; ++j)
            dp[i][j] = -1;
    //先に温度を考慮して分類しておく
    for (int i = 0; i < N; ++i)
    {
        if (T[0] >= A[i] && T[0] <= B[i])
            dp[0][i] = 0;
    }

    for (int i = 1; i < D; ++i)
    {
        for (int j = 0; j < N; ++j)
        { //服の番号
            for (int k = 0; k < N; ++k)
            {
                if (A[k] <= T[i] && B[k] >= T[i] && dp[i - 1][j] != -1)
                {
                    dp[i][k] = max(dp[i][k], dp[i - 1][j] + abs(C[j] - C[k]));
                }
            }
        }
    }

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

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

C++: #include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
typedef long long ll;
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)

int main(void){
	int d, n;//??\??°??????????¨????
	cin >> d >> n;
	vector<int> t(d);
	rep(i, d) cin >> t[i];
	vector<int> a(n), b(n), c(n);//??????????????§????´???????
	rep(i, n) cin >> a[i] >> b[i] >> c[i];

	int dp[201][201];//dp[i][j] i(1~d)??\??????j(0~n)????????????????????????????????§???
	rep(i, 201)rep(j, 201) dp[i][j] = -1;//?????????
	//rep(j, d) dp[0][j] = 0;//?????????
	rep(j, d){
		if(a[j] <= t[0] && t[0] <= b[j]){
			dp[0][j] = 0;
		}
	}
	reps(i, 1, d){//??\
		rep(j, n){//????????????
			rep(k, n){//?????????????????¨??¢?´¢??§??¢????????????
				if(a[k] <= t[i] && t[i] <= b[k] && dp[i - 1][j] != -1){
					dp[i][k] = max(dp[i][k], dp[i - 1][j] + abs(c[k] - c[j]));
					// printf("hikizann %d\n", c[k] - c[j]);
					// printf("i %d j %d k %d dp%d\n", i, j, k, dp[i][k]);
				} 
			}
		}
	}


	int ans = 0;
	rep(i, n){
		ans = max(ans, dp[d - 1][i]);
	}
	printf("%d\n", ans);
	return 0;
}

C++: #include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define LL long long
static const LL INF = 1<<24;
static const int MAX_N = 300;
using namespace std;

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

LL mem[MAX_N][MAX_N];
int N,D;
int Day[MAX_N];
int ans=0;
clothes T;

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

int main(){
    //cout<<-INF<<endl;
    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];
    }
    cout<<cal(1,0)<<endl;
}

C++: #include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
static const int INF = 8931919114514810;
static const int MAX_N = 300;
using namespace std;

int A[300],B[300],C[300];
int mem[MAX_N][MAX_N];
int N,D;
int Day[MAX_N];
int cal(int day,int pp){
   int res=0;
   if(day==N+1){
        return res=0;
   }
   if(mem[day][pp]!=-1){
        return mem[day][pp];
   }
    if(day<=1){
       FOR(i,1,D){
            if(Day[day]>=A[i]&&Day[day]<=B[i]){
            res=cal(day+1,i);
         }
      }
   }
   else{
        FOR(i,1,D){
            if(Day[day]>=A[i]&&Day[day]<=B[i]){
                int temp=abs(C[pp]-C[i]);
                res=max(cal(day+1,i)+temp,res);
                mem[day][pp]=res;
            }
        }
   }
   return mem[day][pp]=res;
}

int main(){
    cin>>N>>D;
    memset(mem,-1,sizeof(mem));
    FOR(i,1,N){
        cin>>Day[i];
    }
    FOR(i,1,D){
        cin>>A[i]>>B[i]>>C[i];
    }
    int ans=0
    FOR(i,1,D){
        if(Day[1]>=A[i]&&Day[1]<=B[i]){
            ans=max(cal(1,i),ans);
        }
    }
    cout<<ans<<endl;
    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[100],B[100],C[150];
};

int N,D;
LL res=-INF;
LL Day[300];
LL mem[300][160][160];
LL s_mem[1000000];
clothes T;

LL cal(LL day,LL p,LL pp,LL sum){
    if(mem[day][p][pp]!=0&&mem[day][p][pp]>=sum){
        res=mem[day][p][pp];
    }
    else{
        if(res<sum+abs(pp-p)&&day==N+1)mem[day][p][pp]=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;
    fill(s_mem,s_mem,-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;
}