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 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=mem[day][pp];
   if(day==N+1){
        return res=0;
   }
   if(mem[day][pp]!=-1){
        return mem[day][pp];
   }
   if(day==0){
         FOR(i,1,D){
                if(Day[1]>=A[i]&&Day[1]<=B[i]){
                res=cal(1,C[i]);
             }
          }
   }

   else{
        if(day<=1){
       FOR(i,1,D){
            if(Day[day]>=A[i]&&Day[day]<=B[i]){
            res=cal(day+1,C[i]);
         }
      }
   }
        FOR(i,1,D){
            if(Day[day]>=A[i]&&Day[day]<=B[i]){
                int temp=abs(pp-C[i]);
                res=max(cal(day+1,C[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];
    }
    cout<<cal(0,0)<<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:n*-1;
}

int main(){
	cin>>d>>n;
	for(int i=0;i<d;i++){
		cin>>tenki[i];
	}
	for(int i=0;i<n;i++){
		cin>>saitei[i]>>saiko[i]>>hade[i];
	}
	for(int i=0;i<d;i++){
		for(int j=0;j<n;j++){
			if(i==0){
				dp[i][j]=0;
			}else{
				if(saitei[j]<=tenki[i]&&tenki[i]<=saiko[j]){
					int A=0;
					for(int k=0;k<n;k++){
						if(saitei[k]<=tenki[i-1]&&tenki[i-1]<=saiko[k]){
							A=max(A,dp[i-1][k]+Abs(hade[k]-hade[j]));
						}
					}
					dp[i][j]=A;
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<n;i++){
		ans=max(ans,dp[d-1][i]);
	}
	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[MAX_N],B[MAX_N],C[MAX_N];
};

int N,D;
LL ans;
LL res;
LL Day[MAX_N];
clothes T;

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


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)<<endl;
}

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

int dp[210][110];
int d,n,t[210],a[210],b[210],c[210];

int main(){
  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 i=0;i<=d;i++)
    for(int j=0;j<=100;j++)dp[i][j] = -1;
  for(int j=0;j<n;j++)
    if(a[j]<=t[0] && t[0]<=b[j])dp[0][c[j]] = 0;

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

  int ans = 0;
  for(int i=0;i<=100;i++)ans = max(ans,dp[d-1][i]);
  cout << ans << endl;
}

C++: #include<bits/stdc++.h>
using namespace std;
int D, N, T[200], A[200], B[200], C[200];
int dp[101];

int main() {
  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];

  fill_n(dp, 101, -1);
  for(int i = 0; i < N; i++) {
    if(B[i] >= T[0] && T[0] >= A[i]) dp[C[i]] = 0;
  }
  for(int i = 1; i < D; i++) {
    for(int j = 0; j <= 100; j++) {
      if(~dp[j]) {
        for(int k = 0; k < N; k++) {
          if(B[k] >= T[i] && T[i] >= A[k]) {
            dp[C[k]] = max(dp[C[k]], dp[j] + max(j - C[k], C[k] - j)); 
          }
        }
      }
    }
  }
  cout << *max_element(dp, dp + 101) << endl;
}

C++: #include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(long long i=0;i<n;++i)
#define REPR(i,n) for(long long i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(long long i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define MOD 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(v) {for(long long sitr=0;sitr<v.size();++sitr){cin>>v[sitr];}}

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

using namespace std;

typedef pair<int,int> pii;


int dp[210][210];

int main(){

  int d, n;
  cin >> d >> n;

  vector<int> t(d), a(n), b(n), c(n);
  REP(i,d){
    cin >> t[i];
  }
  REP(i,n){
    cin >> a[i] >> b[i] >> c[i];
  }

  FOR(i,1,d){
    REP(j,n){
      REP(k,n){
        if(a[j] <= t[i] && t[i] <= b[j] && a[k] <= t[i-1] && t[i-1] <= b[k]){
          dp[i+1][j] = max(dp[i+1][j], dp[i][k] + abs(c[j] - c[k]));
          }
      }
    }
  }

  int ans = 0;
  REP(i,n){
    ans = max(ans, dp[d][i]);
  }

  cout << ans << endl;


  return 0;
}

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

int d,n;
int t[201];
int dp[201][201];
int a[201],b[201],c[201];
int check(int i,int j)
{
  if(i==d-1)
    return 0;
  if(i>=d || j>=n)
    return -999999;
  if(dp[i][j]!=-1)
    return dp[i][j];
  int sum=0;

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

}
int main()
{
  memset(dp,-1,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];
  int ans=0;
  for(int i=0;i<n;i++)
    {
      if(a[i]<=t[0] && t[0]<=b[i])
	ans=max(ans,check(0,i));
    }
  cout<<ans<<endl;
}