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>

#define MAX		220
#define MISS	-100

using namespace std;

struct Huku
{
	//最低気温・最高気温・派手さ
	int max , min , h;
};

int main(void)
{
	int d , n;
	int dp[MAX][MAX] = {0};
	Huku huku[MAX] = {0};
	//日数別気温
	int days[MAX] = {0};
	//前日の派手さ
	int be[MAX][MAX] = {0};

	cin >> d >> n;
	for (int i = 0; i < d; i++)
	{
		cin >> days[i];
	}
	for (int i = 0; i < n; i++)
	{
		cin >> huku[i].min >> huku[i].max >> huku[i].h;
	}

	for (int i = 0; i < n; i++)
	{
		if (huku[i].max >= days[0] && huku[i].min <= days[0])
		{
			be[0][i] = huku[i].h;
		}
		else
		{
			be[0][i] = MISS;
		}
	}

	for (int i = 1; i < d; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (huku[j].max >= days[i] && huku[j].min <= days[i])
			{
				for (int k = 0; k < n; k++)
				{
					//dpの前の部分がMISSなら不可
					if (be[i - 1][k] == MISS)
					{
						continue;
					}

					//現在の派手さと前回に選んだ派手さを比較
					int _max = max(be[i - 1][k] , huku[j].h);
					int _min = min(be[i - 1][k] , huku[j].h);

					if (dp[i][j] <= dp[i - 1][k] + _max - _min)
					{
						dp[i][j] = dp[i - 1][k] + _max - _min;
						be[i][j] = huku[j].h;
					}
				}
			}
		}
	}
	
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		ans = max(ans , dp[d - 1][i]);
	}

	cout << ans << endl;

	return 0;


}

C++: #include<cstdio>
#include <iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<numeric>

#define MOD 1000000007

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

struct data {
	int mi_t;
	int mx_t;
	int c;
};
int d[210];

int main()
{
	int D, N;
	struct data Data[210];
	cin >> D >> N;

	for (int i = 0; i < D; i++) {
		cin >> d[i];
	}

	for (int i = 0; i < N; i++) {
		cin >> Data[i].mi_t >> Data[i].mx_t >> Data[i].c;
	}

	int ans = 0;
	for(int k=0; k<2; k++){
		int total = 0;
		int now_c, next_c = 0;
		for (int i = 0; i < D; i++) {
			int t = d[i];
			int high = 0;
			int low = 100000000;
			for (int j = 0; j < N; j++) {
				if (i % 2 == k) {
					if (t >= Data[j].mi_t && Data[j].mx_t >= t) {
						high = max(high, Data[j].c);
						now_c = high;
					}
				}
				else {
					if (t >= Data[j].mi_t && Data[j].mx_t >= t) {
						low = min(low, Data[j].c);
						now_c = low;
					}
				}
			}
			if(i != 0)
			total += abs(now_c - next_c);
			swap(now_c, next_c);
		}
		ans = max(ans,total);
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

int main(){
	int i,j,k,most,d,n,x,m;
	int dp[201][201];
	int t[201],a[201],b[201],c[201];

	scanf("%d %d",&d,&n);
	for(i=0;i<d;i++) scanf("%d",&t[i]);
	for(i=0;i<n;i++) scanf("%d %d %d",&a[i],&b[i],&c[i]);
	for(i=0;i<d;i++) for(j=0;j<n;j++) dp[i][j]=-1;
	j=0;
	for(i=0;i<n;i++){
		if(a[i]<=t[0] && t[0]<=b[i]){
			dp[0][j]=i;
			j++;
		}
	}
	x=j;
	for(i=0;i<x;i++){
		for(j=1;j<d;j++){
			most=0;
			for(k=0;k<n;k++){
				if(a[k] <= t[j] && t[j] <= b[k]){
					if(most<abs(c[dp[j-1][i]]-c[k])){
						dp[j][i]=k;
						most=abs(c[dp[j-1][i]]-c[k]);
					}
				}
			}
		}
	}
	most=0;
	for(i=0;i<x;i++){
		m=0;
		for(j=1;j<d;j++){
			m+=abs(c[dp[j-1][i]]-c[dp[j][i]]);
		}
		most=max(most,m);
	}
	printf("%d\n",most);
	return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<math.h>
using namespace std;
typedef long long int ll;

int main()
{
	int d,n;
	int t[200];
	int a[200],b[200],c[200];
	int ans=0;
	int ma[200],mi[200];
	int k;

	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<d;i++){
		ma[i]=-1;
		mi[i]=101;
	}

	for(int i=0;i<d;i++){
		for(int j=0;j<n;j++){
			if(a[j]<=t[i]&&t[i]<=b[j]){
				ma[i]=max(ma[i],c[j]);
				mi[i]=min(mi[i],c[j]);
			}
		}
	}

	for(int i=0;i<d;i++){
		if(i==0)
		{
			if(abs(ma[0]-mi[1])>abs(ma[1]-mi[0])){
				k=mi[1];
				ans+=abs(ma[0]-mi[1]);
			}
			else{
				k=ma[1];
				ans+=abs(ma[1]-mi[0]);
			}

		}
		else{
			if(abs(ma[i]-k)>abs(mi[i]-k)){
				ans+=abs(ma[i]-k);
				k=ma[i];
			}
			else{
				ans+=abs(mi[i]-k);
				k=mi[i];
			}
		}
	}

	printf("%d\n",ans);
	return 0;
}

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

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(d, vector<int>(n,-1) );
  for(int i=0;i<n;i++){
    if(a[i] <= t[0] && t[0] <= b[i])dp[0][i] = 0;
  }

  for(int i=1;i<d;i++){
    for(int j=0;j<n;j++){
      if(dp[i-1][j]<0)continue;
      for(int k=0;k<n;k++){
	if(a[k] <= t[i] && t[i] <= b[k]){
	  int dif = abs(c[j] - c[k]);
	  dp[i][k] = max(dp[i][k], dp[i-1][j] + dif);
	}
      }
    }
  }

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

C++: #include<iostream>
#include<algorithm>
#include<complex>
using namespace std;
int dp[201][201],h[201],a[201],b[201],c[201];
int main(){
	int d,n;
	cin>>d>>n;
	for(int i=0;i<d;i++){cin>>h[i];for(int j=0;j<n;j++)dp[i][j]=0;}
	for(int i=0;i<n;i++){cin>>a[i]>>b[i]>>c[i];}
	for(int i=1;i<d;i++)for(int j=0;j<n;j++)if(h[i]>=a[j]&&h[i]<=b[j])for(int k=0;k<n;k++){if(h[i-1]>=a[k]&&h[i-1]<=b[k])dp[i][j]=max(dp[i][j],abs(c[j]-c[k])+dp[i-1][k]);}
	int ans=0;
	for(int i=0;i<n;i++)ans=max(ans,dp[d-1][i]);
	cout<<ans<<endl;
	return 0;
}