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>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef complex<double> P;
typedef pair<int,int> pii;
#define REP(i,n) for(ll i=0;i<n;++i)
#define REPR(i,n) for(ll i=1;i<n;++i)
#define FOR(i,a,b) for(ll i=a;i<b;++i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define MOD (ll)(1e9+7)
#define ADD(a,b) a=((a)+(b))%MOD
#define FIX(a) ((a)%MOD+MOD)%MOD

int main(){
  // D<=200
  // N<=200
  // C<=100
  // NCD <= 4e6 safe
  // dp[d][c] = (d??\????????§c?????????????????????????????§?????????)
  int d,n;
  cin>>d>>n;
  int T[d];
  int A[n],B[n],C[n];
  REP(i,d) cin>>T[i];
  REP(i,n) cin>>A[i]>>B[i]>>C[i];
  int dp[d+1][101];
  REP(i,d+1)REP(j,101)dp[i][j] = -1000000007;
  REP(i,d){
    if(i==0){
      REP(j,n){
        if(!(A[j]<=T[i] && T[i]<=B[j]) )continue;
        dp[i][C[j]] = 0;
      }
    }else{
      // using j
      REP(j,n){
        if(!(A[j]<=T[i] && T[i]<=B[j]) )continue;
        REP(k,101){
          dp[i][C[j]] = max<int>(dp[i][C[j]], dp[i-1][k]+abs(C[j]-k));
        }
      }
    }
  }
  int ans = 0;
  REP(i,101)ans = max(ans,dp[d-1][i]);
  cout<<ans<<endl;
  return 0;
}

C++: #include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int d,n,dp[201][201]={},t[201],a[201],b[201],c[201];
int main(){
	int ans=0;
	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=2;i<=d;i++){
		for(int j=0;j<n;j++){
			if(t[i-1]<=b[j] && t[i-1]>=a[j]){
				for(int k=0;k<n;k++){
					if(t[i-2]<=b[k] && t[i-2]>=a[k]){
					dp[i][j]=max(dp[i][j],abs(c[k]-c[j])+dp[i-1][k]);
					}
				}
			}
		}
	}
	
	for(int i=0;i<n;i++){
		if(ans<=dp[d][i])
		ans=dp[d][i];
	}
	cout<<ans<<endl;
	return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <cstring>
 
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) for(int i = 0; i < (n); i++)
#define MP make_pair
#define X first
#define Y second
#define all(v) v.begin(), v.end()
#define rev(v) v.rbegin(), v.rend()

using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> P;

const int INF = 1<<29;

int dp[201][201];
int T[201];
int A[201], B[201], C[201];

int main(){
	int D, N;
	cin >> D >> N;
	rep(i, D) cin >> T[i];
	rep(i, N) cin >> A[i] >> B[i] >> C[i];

	memset(dp, -1, sizeof(dp));
	rep(i, D){
		rep(j, N){
			if(A[j] > T[i] || B[j] < T[i]) continue;
			if(i == 0){
				dp[i][j] = 0;
			}else{
				rep(k, N){
					if(dp[i-1][k] == -1) continue;
					dp[i][j]= max(dp[i][j], dp[i-1][k]+abs(C[j]-C[k]));
				}
			}
		}
	}
	cout << *max_element(dp[D-1], dp[D-1]+201) << endl;

    return 0;
}

C++: #include <stdio.h>
#include <algorithm>

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

int main(void) {
	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) {
			dp[i][j] = -1;
		}
	}
	for (int i = 0; i < N; ++i) {
		if (A[i] <= T[0] && T[0] <= B[i]) {
			dp[0][i] = 0;
		}
	}
	for (int i = 0; i < D - 1; ++i) {
		for (int j = 0; j < N; ++j) {
			if (dp[i][j] >= 0) {
				for (int k = 0; k < N; ++k) {
					if (A[k] <= T[i + 1] && T[i + 1] <= B[k]) {
						dp[i + 1][k] = std::max(dp[i + 1][k], dp[i][j] + abs(C[j] - C[k]));
					}
				}
			}
		}
	}

	ans = -1;
	for (int i = 0; i < D; ++i) {
		ans = std::max(ans, dp[D - 1][i]);
	}
	printf("%d\n", ans);
	return 0;
}

C++: #include <bits/stdc++.h>
#define range(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, a) range(i, 0, a)
using namespace std;

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];

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

    int ans = 0;
    rep (i, 101) ans = max(ans, dp[d][i]);
    cout << ans << endl;

    return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int a,b,c,d,n,memo[500][500],a1,a2,m1,m2;
vector <pair<int,int> > updown;
vector <int> day;
vector <pair<int,int> > huku;
int solve(int dp,int one,int sum);


int main(){

    cin >> d >> n;
    for(int i=0;i<d;i++){
        cin >> a;
        day.push_back(a);
    }
    for(int i=0;i<n;i++){
        cin >> a >> b >> c;
        updown.push_back(make_pair(a,b));
        huku.push_back(make_pair(c,i));
    }

    std::sort(huku.begin(),huku.end());

    for(int i=0;i<n;i++){
            if(updown[huku[i].second].second>=day[0]&&day[0]>=updown[huku[i].second].first){
                m1=solve(1,huku[i].first,0);
                break;
            }
        }
    for(int i=n-1;i>-1;i--){
            if(updown[huku[i].second].second>=day[0]&&day[0]>=updown[huku[i].second].first){
                m2=solve(1,huku[i].first,0);
                break;
            }
        }


    cout << max(m1,m2) << endl;

return 0;
}


int solve (int dp,int one,int sum){

    //cout << "#######" << endl;

    int s1=0,s2=0;
    if(dp==d)return sum;
    else {
        if(memo[dp][one]!=0)return memo[dp][one];

        for(int i=0;i<n;i++){
            if(updown[huku[i].second].second>=day[dp]&&day[dp]>=updown[huku[i].second].first){
                int sa=max(one,huku[i].first)-min(one,huku[i].first);
                s1=solve(dp+1,huku[i].first,sum+sa);
            }
        }
        for(int i=n-1;i>-1;i--){
            if(updown[huku[i].second].second>=day[dp]&&day[dp]>=updown[huku[i].second].first){
                int sa=max(one,huku[i].first)-min(one,huku[i].first);
                s2=solve(dp+1,huku[i].first,sum+sa);
            }
        }
        return memo[dp][one]=max(s1,s2);
    }

}

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

using namespace std;

const int N = 200;
const int M = 100;

main(){
  int d, n, t[N], a[N], b[N], c[N], dp[N][M+1], ans = 0;
  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(dp[0], dp[N], -1);
  for(int i=0;i<n;i++) if(a[i] <= t[0] && t[0] <= b[i]) dp[0][c[i]] = 0;
  for(int i=1;i<d;i++){
    for(int j=0;j<=M;j++){
      if(dp[i-1][j] == -1) continue;
      for(int k=0;k<n;k++){
        if(a[k] <= t[i] && t[i] <= b[k]){
          int tmp = dp[i-1][j] + abs(c[k] - j);
          if(dp[i][c[k]] < tmp) dp[i][c[k]] = tmp;
        }
      }
    }
  }
  for(int i=0;i<=M;i++) ans = max(ans, dp[d-1][i]);
  cout << ans << endl;
}