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<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];
LL mem[300][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 mem[day][p][pp]=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 "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int D, N, T[212], A[212], B[212], C[212];
int memo[212][212], ans;

int dp(int d, int b)
{
	if (memo[d][b] != -1) { return memo[d][b]; }
	if (d == 0) { return memo[d][b] = 0; }
	int res = 0;
	rep(i, N)
	{
		if (A[i] <= T[d - 1] && T[d - 1] <= B[i])
		{
			memo[d - 1][i] = dp(d - 1, i) + abs(C[b] - C[i]);
			if (d == D) { memo[d - 1][i] -= abs(C[b] - C[i]); }
			res = std::max(res, memo[d - 1][i]);
		}
	}
	return memo[d][b] = res;
}

int main()
{
	memset(memo, -1, sizeof(memo));
	in >> D >> N;
	rep(i, D) { in >> T[i]; }
	rep(i, N) { in >> A[i] >> B[i] >> C[i]; }

	rep(i, N)
	{
		if (A[i] <= T[D - 1] && T[D - 1] <= B[i]) { ans = std::max(ans, dp(D, i)); }
	}

	out << ans << std::endl;
	return 0;
}

C++: #include<iostream>

using namespace std;

int d,n;
int tenki[202];
int saiko[101],saitei[101];
int hade[101];
int dp[201][101];

int abs(int n){
	return n>0?n:-1;
}

int hot(int d,int f){
	if(dp[d][f]!=0)return dp[d][f];
	if(d==0){
		return dp[d][f]=0;
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(saitei[i]<=tenki[d]&&tenki[d]<=saiko[i]){
			ans=max(ans,hot(d-1,i)+abs(hade[i]-hade[f]));
		}
	}
	return dp[d][f]=ans;
}

int main(){
	cin>>d>>n;
	for(int i=1;i<=d;i++){
		cin>>tenki[i];
	}
	for(int i=1;i<=n;i++){
		cin>>saitei[i]>>saiko[i]>>hade[i];
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(saitei[i]<=tenki[d-1]&&tenki[d-1]<=saiko[i]){
			ans=max(ans,hot(d-1,i));
		}
	}
	cout<<ans<<endl;
	return 0;
}

C++: 
#include<algorithm>
#include<iostream>
#include<cstring>

using namespace std;

int D, N, T[200], A[200], B[200], C[200], M[200][100];

int f(int d, int c) {
  int i;

  if(d == D)
    return 0;
  if(M[d][c] >= 0)
    return M[d][c];

  int mx = 0;
  for(i = 0; i < N; ++i) {
    if(A[i] <= T[d] && T[d] <= B[i])
      mx = max(mx, abs(C[i] - c) + f(d + 1, C[i]));
  }

  return M[d][c] = mx;
}

int main() {
  int i;

  cin >> D >> N;
  for(i = 0; i < D; ++i)
    cin >> T[i];
  for(i = 0; i < N; ++i)
    cin >> A[i] >> B[i] >> C[i];

  memset(M, -1, sizeof(M));

  int mx = 0;
  for(i = 0; i < N; ++i) {
    if(A[i] <= T[0] && T[0] <= B[i])
      mx = max(mx, f(1, C[i]));
  }

  cout << mx << endl;
  return 0;
}

C++: #include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;
#define int long long int
const int INF = 1001001001001001LL;

int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

signed main(){
    
    int d, n; cin >> d >> n;
    vector<int> t(d);
    for(int i = 0; i < d; i++) cin >> t[i];
    vector<int> a(n);   
    vector<int> b(n);   
    vector<int> c(n);
    for(int i = 0; i < n; i++) cin >> a[i] >> b[i] >> c[i];

    vector<vector<int> > dp(d + 1, vector<int> (n, -INF));
    for(int j = 0; j < n; j++) dp[0][j] = 0;

    for(int i = 0; i < d; i++){
        for(int j = 0; j < n; j++){
            if(dp[i][j] == -INF) continue;

            for(int k = 0; k < n; k++){
                // 着れるか
                if(a[k] <= t[i] && t[i] <= b[k]){
                    if(i == 0) dp[i + 1][k] = 0;
                    else dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + (int)abs(c[j] - c[k]));
                }
            }
        }
    }

    int ans = 0;
    for(int j = 0; j <= n; j++) ans = max(ans, dp[d][j]);
    cout << ans << endl;
    return 0;
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()

#define PI acos(-1.0)
#define INF 1000000007

typedef long long ll; 
typedef pair<ll, ll> PL;

ll n, d, dp1, dp2, p, q;
ll t[1000], a[1000], b[1000], c[1000], MAX[1000], MIN[1000];

int main(){
	cin >> d >> n;
	REP(i, d){
		cin >> t[i];
	}
	REP(i, n){
		cin >> a[i] >> b[i] >> c[i];
	}
	REP(i, d){
		ll ma = -1, mi = 10000;
		REP(j, n){
			if (t[i] >= a[j] && t[i] <= b[j]){
				ma = max(c[j], ma);
				mi = min(c[j], mi);
			}
		}
		MAX[i] = ma;
		MIN[i] = mi;
	}
	dp1 = 0;
	dp2 = 0;
	REP(i, d - 1){
		p = dp1; q = dp2;
		dp1 = max(p + abs(MAX[i + 1] - MAX[i]), q + abs(MAX[i + 1] - MIN[i]));
		dp2 = max(p + abs(MIN[i + 1] - MAX[i]), q + abs(MIN[i + 1] - MIN[i]));
	}
	cout << max(dp1,dp2) << endl;
}

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

#define loop(i,n) for(int i=1;i<=n;i++)
int dp[202][202];
int t[202];
int a[202],b[202],c[202];

int main(){
  int d,n;
  cin>>d>>n;
  loop(i,d)cin>>t[i];
  loop(j,n)cin>>a[j]>>b[j]>>c[j];
  loop(i,d){
    if(i==1)continue;
    loop(j,n){
      if(t[i]<a[j]||b[j]<t[i])continue;
      loop(k,n){
        if(t[i-1]<a[k]||b[k]<t[i-1])continue;
        dp[i][j]=max(dp[i][j],dp[i-1][k]+abs(c[k]-c[j]));
      }
    }
  }
  int m=0;
  loop(j,n)m=max(m,dp[d][j]);
  cout<<m<<endl;
  return 0;
}