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<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int day[300];
int n, d, y = 1;
int a[300], b[300], c[300];
int mem[210][11000];
int rt = 0;
int solve(int i, int bf);
int main(){
  memset(mem, -1, sizeof(mem));
  int ret = -1;
  cin >> d >> n;
  for(int i = 0; i < d; i++){
    cin >> day[i];
  }
  for(int i = 0; i < n; i++){
    cin >> a[i] >> b[i] >> c[i];
  }
  
  for(int i = 0; i < n; i++){
    if(day[0] >= a[i] && day[0] <= b[i]){
      ret = max(solve(1, c[i]), ret);
    }
  }
  
  cout << ret << endl;
}



int solve(int i, int bf){
  if(i >= d){
    return 0;
  }
  if(mem[i][bf] >= 0) {
    return mem[i][bf];
  }
  int ret = 0;
  for(int j = 0; j < n; j++){
    if(day[i] >= a[j] && day[i] <= b[j]){
      ret = max(solve(i + 1, c[j]) + abs(bf - c[j]), ret);
    }
  }
  return mem[i][bf] = ret;
}

C++: #include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int solve(int hi,int cs);
int d,n;
int t[100];
int ta[111],tb[111],c[111];
int main(){
  cin>>d>>n;
  for(int i=0;i<d;i++){
    cin>>t[i];
  }
  for(int i=0;i<n;i++){
    cin>>ta[i]>>tb[i]>>c[i];
  }
  cout<< solve(0,0)<<endl;;
}
int solve(int hi,int yc){
  int maxx=0;
  if(hi==d){
    return 0;
  }else{
    for(int i=0;i<n;i++){
      if(ta[i]<=t[hi] && t[hi]<=tb[i]){
	maxx=max(maxx,solve(hi+1,c[i])+(hi!=0?abs(yc-c[i]):0));
      }
    }
    return maxx;
  }
}

C++: // JOI 2012-2013 予選4
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<climits>

int D, N;
int T[200];
int A[200], B[200], C[200];
// i日目に服jが着れるか
bool suit[200][200];
// dp[i][j]: i日目に服jを着た時の派手さの差の絶対値の合計の最大値
int dp[200][200];

int main()
{
	std::cin >> D >> N;
	for( int i = 0; i != D; ++i )
		std::cin >> T[i];

	for( int i = 0; i != N; ++i )
		std::cin >> A[i] >> B[i] >> C[i];

	for( int i = 0; i != D; ++i )
	{
		for( int j = 0; j != N; ++j )
		{
			suit[i][j] = A[j] <= T[i] && T[i] <= B[j];

			if( !suit[i][j] )
				dp[i][j] = INT_MIN;
		}
	}

	for( int i = 0; i != D - 1; ++i )
		for( int j = 0; j != N; ++j )
			if( suit[i+1][j] )
				for( int k = 0; k != N; ++k )
					dp[i+1][j] = std::max( dp[i+1][j], dp[i][k] + abs( C[j] - C[k] ) );

	int ans = 0;
	for( int i = 0; i != N; ++i )
		ans = std::max( ans, dp[D - 1][i] );

	std::cout << ans << std::endl;

	return 0;
}

C++: #include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int main()
{
	int d,n;
	cin >> d >> n;
	int dp[205][105];
	for(int i=0;i<205;i++)for(int j=0;j<205;j++)dp[i][j]=1e7;
	int temp[205];
	int a[205],b[205],c[205];
	for(int i=1;i<=d;i++)
	{
		cin >> temp[i];
	}
	for(int i=1;i<=n;i++)
	{
		cin >> a[i]>> b[i] >> c[i];
		if(a[i] <= temp[1] && temp[1] <= b[i])
		{
			dp[1][c[i]]=min(dp[1][c[i]],0);
		}
	}
	for(int i=2;i<=d;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(a[j] <= temp[i] && temp[i] <= b[j])
			{
				for(int k=0;k<=100;k++) dp[i][c[j]]=min(dp[i][c[j]],dp[i-1][k]+abs(k-c[j]));
			}
		}
	}
	int val=1e7;
	for(int k=0;k<=100;k++) val=min(val,dp[d][k]);
	cout << val << endl;
}

C++: #include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define LL long long
static const LL INF = 1<<60;
static const int MAX_N = 300;
using namespace std;

struct clothes{
    LL A[MAX_N],B[MAX_N],C[MAX_N];
};

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

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

int main(){
    cin>>N>>D;
    fill(mem[0],mem[MAX_N],-1);
    FOR(i,1,N){
        cin>>Day[i];
    }
    FOR(i,1,D){
        cin>>T.A[i]>>T.B[i]>>T.C[i];
    }
    cout<<cal(1,0)<<endl;
}

C++: #include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int d, n, t[200], a[200], b[200], c[200], dp[200][200] = {0};
int hds(int day, int sh){
  if(day == d) return 0;
  if(dp[day][sh]) return dp[day][sh];
  int ret = 0, v = 0;
  for(int i = 0; i < n; i++){
    if(a[i] <= t[day] && t[day] <= b[i]){
      if(day) v = abs(sh - c[i]);
      else v = 0;
      ret = max(ret, hds(day+1, c[i]) + v);
    }
  }
  return dp[day][sh] = ret;
}
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];
  cout << hds(0, 0) << endl;
}

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

int N , D ;
int T[210] ;
int W[210][3] ;

int dp[210][210] ;

int a( int x , int y ){
	int z = x - y ;
	if( z < 0 ) z *= -1 ;
	return z ;
}

int f( int day , int p ){
	if( day == D-1 ) return 0 ;
	if( dp[day][p] != -1 ) return dp[day][p] ;
	
	int ans = 0 ;
	for( int i=0 ; i<N ; i++ ){
		if( W[i][0] <= T[day+1] && W[i][1] >= T[day+1] ){
			ans = max( ans , a( W[p][2] , W[i][2] ) + f( day+1 , i ) ) ;
		}
	}
	
	return dp[day][p] = ans ;
}

int main(){
	
	cin >> D >> N ;
	for( int i=0 ; i<D ; i++ ) cin >> T[i] ;
	for( int i=0 ; i<N ; i++ ){
		cin >> W[i][0] ; // 下限
		cin >> W[i][1] ; // 上限
		cin >> W[i][2] ; // コスト
	}
	
	for( int i=0 ; i<210 ; i++ ){
		for( int j=0 ; j<210 ; j++ ){
			dp[i][j] = -1 ;
		}
	}
	
	int best = 0 ;
	for( int i=0 ; i<N ; i++ ){
		if( W[i][0] <= T[0] && W[i][1] >= T[0] ){
			best = max( best , f(0,i) ) ;
		}
	}
	
	cout << best << endl ;
	
return 0;
}

C++: #include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
 
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
    return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

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

    // dp[i][j] := i日目に服jをきた時の最大値
    auto dp = make_v(d + 1, n, 0);

    // i日目に服jを着ることが可能か
    auto check = [&](int i, int j) {
        return a[j] <= t[i] && t[i] <= b[j];
    };

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

    int ans = *max_element(dp[d - 1].begin(), dp[d - 1].end());
    
    cout << ans << endl;

    return 0;
}