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<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;

struct str
{
	int a, b, c;
	void new_str(int a_, int b_, int c_){
		a = a_; b = b_; c = c_;
	}
};
int dp[200][200];
int t[200];
str cl[200];
int main(){
	int d, n;
	scanf("%d%d", &d, &n);
	memset(dp, -1, sizeof(dp));
	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);
		cl[i].new_str(a, b, c);
	}
	for (int i = 0; i < n; i++)
		if (cl[i].a <= t[0] && t[0] <= cl[i].b)
			dp[0][i] = 0;
	for (int i = 1; i < d; i++){
		for (int j = 0; j < n; j++){
			if (cl[j].a <= t[i] && t[i] <= cl[j].b){
				for (int l = 0; l < n; l++){
					if (dp[i - 1][l] >= 0 && abs(cl[l].c - cl[j].c) + dp[i - 1][l]>dp[i][j])
						dp[i][j] = abs(cl[l].c - cl[j].c) + dp[i - 1][l];
				}
			}
		}
	}
	printf("%d\n", *max_element(dp[d - 1], dp[d - 1] + n));
	return 0;
}

C++: #include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef double db;
ll D,N,T[200],A[200],B[200],C[200];
ll dp[200][200];//day: i   clothes: j  maximum C
int main()
{
	scanf("%lld%lld",&D,&N);
	for(ll i=0;i<D;i++){
		scanf("%lld",&T[i]);
	}
	for(ll i=0;i<N;i++){
		scanf("%lld%lld%lld",&A[i],&B[i],&C[i]);
	}
	for(ll i=0;i<N;i++){
		if(T[0]<A[i]||B[i]<T[0]) dp[0][i]=-1;
	}
	for(ll i=1;i<D;i++){
		for(ll j=0;j<N;j++){
			if(T[i]<A[j]||B[j]<T[i]) dp[i][j]=-1;
			else{
				for(ll k=0;k<N;k++){
					if(dp[i-1][k]>=0) dp[i][j]=max(dp[i][j],dp[i-1][k]+abs(C[j]-C[k]));
				}
			}
		}
	}
	ll ans=0;
	for(ll i=0;i<N;i++) ans=max(ans,dp[D-1][i]);
	printf("%lld\n",ans);
}

C++: #include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
#define INF (-1 * (1 << 29))
using namespace std;

struct Clothes{
    int low, up, glitz;
};

int dp[205][205], t[205];
Clothes c[205];

void update(int day, int now, int before){
    if(c[now].low <= t[day] && c[now].up >= t[day]){
        if(day == 0) dp[day][now] = 0; //テ・ツ按敕ヲツ猟・テ」ツ?ォテァツ敖?」ツつ凝ヲツ慊?
        else if(dp[day - 1][before] != INF){
            dp[day][now] = max(dp[day][now], dp[day - 1][before] + abs(c[before].glitz - c[now].glitz)); 
        }
    }
}

int solve(int d, int n){
    rep(day,d){
        rep(now,n){
            rep(before,n){
                update(day, now, before);
            }
        }
    }

/*
    rep(i,d){
        rep(j,n){
            cout << dp[i][j] << ' ';
        }
        cout << endl;
    }
*/

    int retval = 0;
    rep(i,n) retval = max(retval, dp[d - 1][i]);
    return retval;
}

int main(){
    int d, n;

    cin >> d >> n;
    rep(i,d) cin >> t[i];
    rep(i,n) cin >> c[i].low >> c[i].up >> c[i].glitz;
    rep(i,205) rep(j,205) dp[i][j] = INF;
    cout << solve(d, n) << endl;
}

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

using namespace std;

int D, N;
vector<int> T;
vector<int> A, B, C;
vector<vector<bool>> usable;
vector<vector<int>> dp;

int main() {
  cin >> D >> N;
  T.assign(D + 1, 0);
  A.assign(N + 1, 0);
  B.assign(N + 1, 0);
  C.assign(N + 1, 0);
  usable.assign(D + 1, vector<bool>(N + 1, false));
  dp.assign(D + 1, vector<int>(N + 1, -1));
  for (int i = 1; i <= D; i++)
    cin >> T[i];
  for (int i = 1; i <= N; i++)
    cin >> A[i] >> B[i] >> C[i];
  for (int i = 1; i <= D; i++)
    for (int k = 1; k <= N; k++)
      usable[i][k] = (A[k] <= T[i] && T[i] <= B[k]);

  for (int i = 1; i <= N; i++)
    if (usable[1][i])
      dp[1][i] = 0;
  for (int i = 1; i <= D - 1; i++)
    for (int k = 1; k <= N; k++)
      if (dp[i][k] >= 0)
        for (int j = 1; j <= N; j++)
          if (usable[i + 1][j])
            if (dp[i + 1][j] < dp[i][k] + abs(C[k] - C[j]))
              dp[i + 1][j] = dp[i][k] + abs(C[k] - C[j]);
  int ans=-1;
  for(int i=1;i<=N;i++){
    if(ans < dp[D][i]){
      ans = dp[D][i];
    }
  }
  cout << ans << endl;
}

C++: #include<bits/stdc++.h>
#define LL long long
#define FOR(i,a,b) for(int i=a;i<=b;++i)

using namespace std;

static const LL MAX_N = 1e+5;
static const LL INF = 1 << 25;

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

int N,D;
LL res=-INF;
LL Day[300];
LL mem[300][160][160];
LL s_mem[1000000];
clothes T;

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


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

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

using namespace std;

inline int to_int(string s) {int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string to_str(T x) {ostringstream sout; sout << x; return sout.str();}

typedef long long ll;

int main()
{
	int d, n, T[256], low[256], hi[256], M[256];
	int dp[256][256]; //dp[i][j] : i日目に服jを着た時の派手さの最大値

	cin >> d >> n;

	for(int i = 0; i < d; i++)
	{
		cin >> T[i];
	}
	for(int i = 0; i < n; i++)
	{
		cin >> low[i] >> hi[i] >> M[i];
	}	

	for(int i = 0; i < 201; i++)
	{
		for(int j = 0; j < 201; j++)
		{
			dp[i][j] = 0;
		}
	}

	int res = 0;

	for(int i = 1; i < d; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(T[i] >= low[j] && T[i] <= hi[j])
			{
				for(int k = 0; k < n; k++)
				{
					if(low[k] <= T[i-1] && hi[k] >= T[i-1])
					{
						dp[i][j] = max(dp[i][j], abs(M[j]-M[k])+ dp[i-1][k]);
						res = max(res, dp[i][j]);
					}
				}
			}
		}
	}

	cout << res << endl;
}