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<stdio.h>
#include<stdlib.h>
int h[201][201];
int main(void)
{
    int n,m,i,j,x[200],a[200],b[200],c[200],l,s,w,f;
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++){
	    scanf("%d",&x[i]);
	}
	for(i=0;i<m;i++){
	    scanf("%d %d %d",&a[i],&b[i],&c[i]);
	}
	for(i=0;i<n;i++){
	    for(j=0;j<m;j++){
		    h[i][j]=0;
		}
	}
	for(i=0;i<n;i++){
	    for(j=0;j<m;j++){
		    if(x[i]>=a[j]&&x[i]<=b[j]){
			    h[i][j]=c[j];
			}
		}
	}
	w=0;
	for(i=0;i<n-1;i++){
	    s=0;
		for(j=0;j<m;j++){
		    for(l=0;l<m;l++){
			    f=abs(h[i][j]-h[i+1][l]);
				if(h[i][j]!=0&&h[i+1][l]!=0&&s<f){
				    s=f;
				}
			}
		}
		w+=s;
	}
	printf("%d\n",w);
	return 0;
}

C++: #include<iostream>
using namespace std;
//dp[i][j]: i??\???j???????????????c_x_(i)-c_x_(i-1)????????§???
int dp[201][201];
int main(){
    int d,n,ans=0;
    cin>>d>>n;
    int a[201],b[201],c[201],tem[201];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<d;i++)
        cin>>tem[i];
    for(int i=0;i<n;i++)
        cin>>a[i]>>b[i]>>c[i];
    for(int m=1;m<d;m++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                if(a[i]<=tem[m]&&tem[m]<=b[i]  &&  a[j]<=tem[m-1]&&tem[m-1]<=b[j])
                    dp[m][i]=max(dp[m][i],abs(c[i]-c[j])+dp[m-1][j]);
    for(int i=0;i<n;i++)
        ans=max(ans,dp[d-1][i]);
    cout<<ans<<endl;
}

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>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

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

int 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), b(N), c(N);
    for(int i=0; i<N; i++) cin>>a[i]>>b[i]>>c[i];

    vector<vector<int>> dp(N+10, vector<int>(1010, 0));

    vector<bool> valid(110, false);
    for(int i=0; i<N; i++){
        if(a[i] <= t[0] && t[0] <= b[i]){
            valid[c[i]] = true;
        }
    }

    for(int i=1; i<D; i++){
        for(int j=0; j<N; j++){
            for(int k=0; k<=100; k++){
                //if(dp[i][k] == 0) continue;

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

    /*
    for(int i=0; i<=100; i++){
        cout << i << " " << dp[2][i] << endl;
    }*/

    int ans = 0;
    for(int i=0; i<=100; i++){
        ans = max(ans, dp[D][i]);
    }

    cout << ans << endl;
}

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

struct str
{
	int a, b, c;
};
int t[200];
str b[200];
str dp[200];
int main(){
	int d, n;
	scanf("%d%d", &d, &n);
	for (int i = 0; i < d; i++)
		scanf("%d", &t[i]);
	for (int i = 0; i < n; i++){
		int a_, b_, c_;
		scanf("%d%d%d", &a_, &b_, &c_);
		b[i].a = a_;
		b[i].b = b_;
		b[i].c = c_;
	}
	int min = 101;
	for (int i = 0; i < n; i++)
		if (b[i].a <= t[0] && t[0] <= b[i].b&&min >= b[i].c)
			min = b[i].c;
	dp[0].a = 0; dp[0].b = min;
	for (int i = 1; i < d; i++){
		int max = 0;
		for (int j = 0; j < n; j++){
			if (b[j].a <= t[i] && t[i] <= b[j].b&&abs(dp[i - 1].b - b[j].c) >= max){
				max = abs(dp[i - 1].b - b[j].c);
				dp[i].b = b[j].c;
			}
		}
		dp[i].a = dp[i - 1].a + max;
	}
	printf("%d\n", dp[d - 1]);
	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, p = 0, dp1, dp2;
ll t[1000], a[1000], b[1000], c[1000], MAX[1000], MIN[1000];

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

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

using namespace std;

#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int d,n;
int t[210];
int a[210],b[210],c[210];
int dp[210][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<n; j++){
			if(a[j] <= t[i] && t[i] <= b[j]){
				dp[i][j] = 0;
			}
			else{
				dp[i][j] = -INF;
			}
		}
	}
	//????????????????????§?????????????????\???????????¨??§?????????????????¨?????¨????????????


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

	int max = 0;

	for(int i=0; i < n; i++){
		if(dp[0][i] > max){
			max = dp[0][i];
		}
	}

	cout << max << endl;

}