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 pb(n) push_back(n)
#define fi first
#define se second
#define X real()
#define Y imag()
#define value(x,y,w,h) (x >= 0 && x < w && y >= 0 && y < h)
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

typedef long long ll ;
typedef deque<int> di ;
typedef deque<ll> dl ;
typedef map<string,int> dict;
typedef complex<double> comd;
typedef pair<int,int> pii;

constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0};
const int dx[] = {0,-1,0,1};

double CalcDist(comd p1, comd p2){
  return sqrt(pow(p1.X - p2.X,2.0) + pow(p1.Y -p2.Y,2.0));
}

template <typename T>
void out(deque < T > d)
{
  for(size_t i = 0; i < d.size(); i++)
  {
    debug(d[i]);
  }
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

int dp[2][200];
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N,D;
  cin >> N >> D;
  vector<int> d(N),a(D),b(D),c(D);
  vector<int> day[N];
  rep(i,N){
    cin >> d[i];
  }
  rep(i,D){
    cin >> a[i] >> b[i] >> c[i];
  }
  rep(j,N){
    int u = 0;
    rep(i,D){
      if(a[i] <= d[j] && d[j] <= b[i]){
        ++u;
        day[j].pb(c[i]);
      }
    }
    sort(all(day[j]));
  }
//   rep(j,N){
//     rep(i,day[j].size()){
//       cout << day[j][i] << " " ;
//     }
//     cout << endl;
//   }
  int ans = 0;
  REP(i,0,N-1){
    int lm = 0,hm = 0;
    lm = abs(day[i][0]-day[i+1][0]);
    dp[0][i+1] = dp[0][i] + lm;
//     debug(dp[0][i+1]);

    lm = max(lm,abs(day[i][0]-day[i+1][day[i+1].size()-1])) ;
    dp[1][i+1] = dp[0][i]+ lm;
//     debug(dp[1][i+1]);

    if(day[i].size() != 1){
      hm = abs(day[i][day[i].size()-1]-day[i+1][0]);
      if(dp[0][i+1] < dp[1][i] +hm){
        dp[0][i+1] = dp[1][i] + hm;
      }
//       debug(dp[0][i+1]);

      hm = max(hm,abs(day[i][day[i].size()-1]-day[i+1][day[i+1].size()-1])) ;
      if(dp[1][i+1] < dp[1][i] + hm){
        dp[1][i+1] = dp[1][i] +hm;
      }
//       debug(dp[1][i+1]);
    }
  }
  cout << max(dp[0][N-1],dp[1][N-1]) << endl;
  return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#define loop(i,b,n) for(int i = b; i<n; i++)
#define rep(i,n)  loop(i,0,n)
#define INF 10000
using namespace std;

int main (){
    
    int d,number;
    int temp[202] = {0};
    int dp[500][500];
    rep(i,500)
        rep(j,500)
    dp[i][j] = -INF;
     //(x,y) = (day,hade)
    int Min[210],Max[210],c[210];
   // bool check[500][500];
    /*rep(i,501)
       rep(j,501)
            check[i][j] = false;*/
    cin  >> d >> number;
    rep(i,d)
        cin >> temp[i+1];
    rep(i,number)
        cin >> Min[i+1] >> Max[i+1] >> c[i+1];
    loop(j,0,d+1)//day
    {
        
        loop(k,0,number+1)// k
        {
            if(Min[k] <= temp[j] && temp[j] <=Max[k])
            {
                if(j == 1)
                    dp[j][c[k]] = 0;
                else
                {
                    dp[j][c[k]] = 0;
                    loop(l,0,500)
                    {
                        if(dp[j-1][l] != -INF)
                        {
                            dp[j][c[k]] = max(abs(c[k]-l)+dp[j-1][l],dp[j][c[k]]+dp[j-1][l]);
                            //cout << abs(c[k]-l)<< " " ;
                        }
                        
                        
                    }
                    
                    
                }	
            }
            
        }
        
    }
    
    int answer = 2;
    rep(i,500)
        answer = max(answer,dp[d][i]);
    cout << answer << endl;
    
    return 0;
}

C++: #include "stdio.h"

int day;
int num;
int temp[201];
int wear[200];
int dp[201][200] = {};
int min[201] = {};
int max[201] = {};
int ans=0;

int abs(int a) {
	if (a > 0)return a;
	return -a;
}

int Max(int a, int b) {
	if (a > b)return a;
	return b;
}

int main() {
	scanf("%d %d", &day, &num);
	for (int i = 0; i < day; i++) {
		scanf("%d", &temp[i + 1]);
	}
	for (int i = 0; i < num; i++) {
		scanf("%d %d %d", &min[i], &max[i], &wear[i]);
	}
	for (int i = 2; i <= day; i++) {
		for (int j = 0; j < num; j++) {
			if (temp[i] >= min[j] && temp[i] <= max[j]) {
				for (int k = 0; k < num; k++) {
					if (temp[i-1] >= min[k] && temp[i-1] <= max[k]) {
						dp[i][j] = Max(dp[i][j], dp[i - 1][k] + abs(wear[k] - wear[j]));
					}
				}
			}
		}
	}
	for (int i = 0; i < num; i++)ans = Max(ans, dp[day][i]);
	printf("%d\n", ans);
	return 0;

}

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

int z(int x){
	if(x<0)x=-x;
	return x;
}

int main(){
	int d,n,a[200],b[200],c[200],t[200],dp[200][200];
	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<200;i++)for(int j=0;j<200;j++)dp[i][j]=-1;
	for(int j=0;j<n;j++)if(a[j]<=t[0]&&t[0]<=b[j])dp[0][j]=0;
	for(int i=1;i<d;i++){
		for(int j=0;j<n;j++){
			for(int k=0;k<n;k++){
				int e=-1;
				if(dp[i-1][k]!=-1&&a[j]<=t[i]&&t[i]<=b[j])e=dp[i-1][k]+z(c[k]-c[j]);
				if(e>dp[i][j])dp[i][j]=e;
			}
		}
	}
	int ans=0;
	for(int j=0;j<n;j++){
		if(dp[d-1][j]>ans)ans=dp[d-1][j];
	}
	printf("%d\n",ans);
}

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

int dp[201][201], d, n, t[201], a[201], b[201], c[201], mx = 0;

int abs(int x, int y)
{
	if (x >= y) return x - y;
	else return y - x;
}

int main()
{
	cin >> d >> n;
	for (int i = 1; i <= d; i++){
		cin >> t[i];
	}
	for (int i = 1; i <= n; i++){
		cin >> a[i] >> b[i] >> c[i];
	}
	memset(dp, -1, sizeof dp);

	for (int i = 1; i <= n; i++){
		if (a[i] <= t[1] && t[1] <= b[i]){
			dp[1][i] = 0;
		}
	}

	//dp
	for (int today = 2; today <= d; today++){
		for (int n2 = 1; n2 <= n; n2++){
			for (int n1 = 1; n1 <= n; n1++){
				if (dp[today - 1][n1] == -1) continue;
				if (a[n2] > t[today] || t[today] > b[n2]) continue;
				dp[today][n2] = max(dp[today][n2], dp[today - 1][n1] + abs(c[n1], c[n2]));
			}
		}
	}

	for (int i = 1; i < n; i++){
		mx = max(dp[d][i], mx);
	}
	cout << mx << endl;
	return 0;
}