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 <bits/stdc++.h>
using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;

const long long INF = 1LL << 60;

int main()
{
    int D, N;
    cin >> D >> N;

    vector<int> tem(D);
    rep(i, D) cin >> tem[i];

    vector<vector<int>> cloth(N, vector<int>(3));
    rep(i, N) cin >> cloth[i][0] >> cloth[i][1] >> cloth[i][2];

    vector<vector<int>> dp(D, vector<int>(N, -1));

    rep(i, N) {
        if (cloth[i][0] <= tem[0] && cloth[i][1] >= tem[0]) {
            dp[0][i] = 0;
        }
    }

    repd(i, 1, D) {
        rep(j, N) {
            if (cloth[j][0] <= tem[i] && cloth[j][1] >= tem[i]) {
                rep(k, N) {
                    if (dp[i-1][k] != -1) {
                        chmax(dp[i][j], dp[i-1][k] + abs(cloth[j][2] - cloth[k][2]));
                    }
                }
            }
        }
    }

    int ans = 0;
    rep(i, N) {
        ans = max(ans, dp[D-1][i]);
    }

    cout << ans << endl;

    return 0;
}

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

int dp[100][2][3];

int main(){
	int n,k,a[100],b[100];
	scanf("%d%d",&n,&k);
	dp[0][0][0]=dp[0][0][1]=dp[0][0][2]=1;
	for(int i=0;i<k;i++){
		scanf("%d%d",&a[i],&b[i]);
		for(int j=0;j<3;j++) if(b[i]!=j+1) dp[a[i]-1][0][j]=dp[a[i]-1][1][j]=-1;
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<3;j++){
			if(dp[i][0][j]==-1) continue;
			for(int k=0;k<3;k++){
				if(k==j) dp[i][1][j]=(dp[i][1][j]+(dp[i-1][0][k]==-1?0:dp[i-1][0][k]))%10000;
				else dp[i][0][j]=(dp[i][0][j]+(dp[i-1][0][k]==-1?0:dp[i-1][0][k])+(dp[i-1][1][k]==-1?0:dp[i-1][1][k]))%10000;
			}
		}
	}
	int res=0;
	for(int i=0;i<3;i++) res+=(dp[n-1][0][i]==-1?0:dp[n-1][0][i])+(dp[n-1][1][i]==-1?0:dp[n-1][1][i]);
	res%=10000;
	printf("%d\n",res);
}

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

struct CLOTHES{
    int a;
    int b;
    int c;
};

int dp[256][256] = { 0 };

int main(){
    int d,n;
    cin >> d >> n;
    int t[256];
    for(int i = 1; i <= d; i++){
        cin >> t[i];
    }
    CLOTHES clo[256];
    for(int i = 1; i <= n; i++){
        cin >> clo[i].a >> clo[i].b >> clo[i].c;
    }
    
    int maxi = 0, sum = 0;
    for(int i = 1; i <= d; i++){
        maxi = 0;
        for(int i2 = 1; i2 <= n; i2++){
            if(t[i] >= clo[i2].a && t[i] <= clo[i2].b){
                for(int j = 1; j <= n; j++){
                    if(dp[i - 1][j] != -1){
                        dp[i][i2] = max(dp[i][i2], abs(clo[j].c - clo[i2].c));
                    }
                }
            }
            else{ dp[i][i2] = -1; }
            maxi = max(maxi,dp[i][i2]);
        }
        if(i != 1){ sum += maxi; }
    }

    cout << sum << endl;
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
int dp[300][110],l[300],r[300],p[300],n,m,a[300];
int main(){
	cin>>n>>m;for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<m;i++)cin>>l[i]>>r[i]>>p[i];
	for(int i=0;i<33000;i++)dp[i/110][i%110]=-1000000000;
	for(int i=0;i<m;i++){
		if(l[i]<=a[0] && a[0]<=r[i]){
			dp[0][p[i]]=max(dp[0][p[i]],0);
		}
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<=100;j++){
			for(int k=0;k<m;k++){
				if(l[k]<=a[i] && a[i]<=r[k]){
					dp[i][p[k]]=max(dp[i][p[k]],dp[i-1][j]+abs(j-p[k]));
				}
			}
		}
	}
	int maxn=0;for(int i=0;i<=100;i++)maxn=max(maxn,dp[n-1][i]);
	cout<<maxn<<endl;
	return 0;
}

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

struct Cloth
{
	int mini, maxi, glitz;
	bool operator<(const Cloth& c) const
	{
		if (this->glitz < c.glitz) return true;
		else if (this->glitz == c.glitz){
			if (this->mini < c.mini) return true;
			else if (this->mini == c.mini && this->maxi < c.maxi) return true;
			return false;
		}
		return false;
	}
};

int d, n;
int temp[256];
Cloth cloth[256];
int memo[256][256];

int solve(int day, int before);

int main()
{
	scanf("%d %d", &d, &n);
	for (int i = 1; i <= d; i++) scanf("%d", temp + i);
	for (int i = 1; i <= n; i++){
		scanf("%d %d %d", &cloth[i].mini, &cloth[i].maxi, &cloth[i].glitz);
	}
	cloth[0] = cloth[1];
	//sort(cloth, cloth + n);
	memset(memo, -1, sizeof(memo));
	
	solve(1, 0);
	int maxi = 0;
	for (int i = 1; i <= d; i++){
		for (int j = 1; j <= n; j++){
			//printf("%d ", memo[i][j]);
			maxi = max(maxi, memo[i][j]);
		}
		//puts("");
	}
	printf("%d\n", maxi);
	
	return 0;
}

int solve(int day, int before)
{
	if (day > d) return 0;
	if (memo[day][before] >= 0) return memo[day][before];
	
	int t = INT_MIN;
	for (int i = 1; i <= n; i++){
		if (cloth[i].mini <= temp[day] && temp[day] <= cloth[i].maxi){
			if (memo[day][i] == -1) memo[day][i] = 0;
			//printf("%*d %d\n", day, day, i);
			solve(day + 1, i);
			t = max(t, solve(day + 1, i) + abs(cloth[before].glitz - cloth[i].glitz));
			//printf("%*s %d\n", day, "", t);
		}
	}
	
	return memo[day][before] = t;
}

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

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int main(){
  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];
  const int M = 101;
  int dp[200][101] = {};
  REP(i, D)REP(j, M) dp[i][j] = -INF;
  REP(j, N) {
    if(A[j] <= T[0]  && T[0] <= B[j]) dp[0][C[j]] = 0;
  }
  FOR(i, 1, D){
    REP(j, N) if(A[j] <= T[i] && T[i] <= B[j]){
      REP(k, M) {
        dp[i][C[j]] = max(dp[i][C[j]], dp[i - 1][k] + abs(C[j] - k));
      }
    }
  }
  int ans = 0;
  REP(k, M) ans = max(ans, dp[D - 1][k]);
  cout<<ans<<endl;
  return 0;
}