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 llong long long 
typedef struct data{
	int low;
	int high;
	int eva;
}data;
int D, N;
int temp[201];
data kind[200];
int score[201][200];

int solve(int d, int k, int e){
	//cout << d << " " << k << " " << e << "   " << score[d][k] << endl;
	score[d][k] = e;
	if(score[d][k] > e) return 0;
	if(d == D) return e;
	int ret = 0;
	for(int i = 0; i < N; i++){
		data use = kind[i];
		if(use.low > temp[d + 1] || use.high < temp[d + 1]) continue;
		if(d > 0) ret = max(ret, solve(d + 1, i, e + fabs(kind[k].eva - kind[i].eva)) );
		else ret = max(ret, solve(d + 1, i, 0));
	}

	return ret;
}

int main(){
	fill_n(temp, 201, -1);
	fill_n(*score, 201 * 200, 0);
	cin >> D >> N;
	for(int i = 1; i <= D; i++){
		cin >> temp[i];
	}
	for(int i = 0; i < N; i++){
		cin >> kind[i].low >> kind[i].high >> kind[i].eva;
	}

	cout << solve(0, 0, -1) << endl;
	return 0;
}

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

struct str
{
	int a, b, c;
};
int t[200];
str b[200];
str dp1[200];
str dp2[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;
	dp1[0].a = 0; dp1[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(dp1[i - 1].b - b[j].c) >= max){
				max = abs(dp1[i - 1].b - b[j].c);
				dp1[i].b = b[j].c;
			}
		}
		dp1[i].a = dp1[i - 1].a + max;
	}
	int ma = 0;
	for (int i = 0; i < n; i++)
		if (b[i].a <= t[0] && t[0] <= b[i].b&&ma< b[i].c)
			ma = b[i].c;
	dp2[0].a = 0; dp2[0].b = ma;
	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(dp2[i - 1].b - b[j].c) >= max){
				max = abs(dp2[i - 1].b - b[j].c);
				dp2[i].b = b[j].c;
			}
		}
		dp2[i].a = dp2[i - 1].a + max;
	}
	printf("%d\n", dp2[d - 1]);
	return 0;
}

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

using namespace std;

const int N = 200;
const int INF = (1<<28);

main(){
  int d, n, t[N], a[N], b[N], c[N], dp[200][101], ans = 0;
  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];
  fill(dp[0], dp[2], -1);
  for(int i=0;i<n;i++) if(a[i] <= t[0] && t[0] <= b[i]) dp[0][c[i]] = 0;
  for(int i=1;i<d;i++){
    for(int j=0;j<=100;j++){
      if(dp[i-1][j] == -1) continue;
      for(int k=0;k<n;k++){
        if(a[k] <= t[i] && t[i] <= b[k]){
          int tmp = dp[i-1][j] + abs(c[k] - j);
          if(dp[i][c[k]] < tmp) dp[i][c[k]] = tmp;
        }
      }
    }
  }
  for(int i=0;i<=100;i++) ans = max(ans, dp[d-1][i]);
  cout << ans << endl;
}

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, dp;
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;
	}
	REP(i, n - 1){
		if (i == 0){
			if (abs(MAX[i + 1] - MIN[i]) > abs(MIN[i + 1] - MAX[i])){
				p += abs(MAX[i + 1] - MIN[i]);
				dp = MAX[i + 1];
			}
			else{
				p += abs(MIN[i + 1] - MAX[i]);
				dp = MIN[i + 1];
			}
		}
		else{
			if (abs(MAX[i + 1] - dp) > abs(MIN[i + 1] - dp)){
				p += abs(MAX[i + 1] - dp);
				dp = MAX[i + 1];
			}
			else{
				p += abs(MIN[i + 1] - dp);
				dp = MIN[i + 1];
			}
		}
	}
	cout << p << endl;
}

C++: #include <iostream>
#include <limits>
#include <cmath>

constexpr int MAX = 200;
constexpr int MAX_C = 100;

int D, N, T[MAX], A[MAX], B[MAX], C[MAX];
int memo[MAX_C + 1][MAX + 1];

int solve(int tmp, int n = 1);

int main(){
	std::ios::sync_with_stdio(false);
	
	memset(memo, -1, sizeof(memo));

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

	int ans = 0;
	for(int i = 0; i < N; ++i){
		if(A[i] <= T[0] && T[0] <= B[i]){
			ans = std::max(ans, solve(C[i]));
		}
	}

	std::cout << ans << std::endl;
	return 0;
}

int solve(int tmp, int n){
	if(n == D){
		return 0;
	}
	if(memo[tmp][n] != -1){
		return memo[tmp][n];
	}

	int res = 0;
	for(int i = 0; i < N; ++i){
		if(A[i] <= T[n] && T[n] <= B[i]){
			res = std::max(res, solve(C[i], n + 1) + abs(tmp - C[i]));
		}
	}
	//std::cout << "memo[" << tmp << "][" << n << "] = " << res << std::endl;
	return memo[tmp][n] = res;
}

C++: #include<iostream>

int main(){
	//Cs[i][0]: min, Cs[i][1]: max, Cs[i][2]: 派手さ
	//dp[i][j]: i日目に服jを着た時の派手さの最大値
	int D, N, Ts[200], Cs[200][3], dp[200][200];
	const int INF = 1 << 24;

	std::cin >> D >> N;
	for(int i=0;i<D;i++){
		std::cin >> Ts[i];
	}
	for(int j=0;j<N;j++){
		std::cin >> Cs[j][0] >> Cs[j][1] >> Cs[j][2];
	}

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

	int res = 0;
	for(int i=1;i<D;i++){
		for(int j=0;j<N;j++){
			if(Cs[j][0] <= Ts[i] && Ts[i] <= Cs[j][1]);
			else continue;
			for(int k=0;k<N;k++){
				if(Cs[k][0] <= Ts[i-1] && Ts[i-1] <= Cs[k][1]);
				else continue;
				dp[i][j] = std::max(dp[i][j], std::abs(Cs[j][2]-Cs[k][2]) + dp[i-1][k]);
				res = std::max(res, dp[i][j]);
			}
		}
	}

	std::cout << res << std::endl;
}