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<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<set>
#include<tuple>
#include<stack>


using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpl;
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };

#define ARRAY_MAX 305

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;

ll dp[ARRAY_MAX][ARRAY_MAX];
ll N, D;
vector<ll> d, a, b, c;

ll dfs(ll day,ll num){

	//day日目に服numを着る場合

	if (day == 1)
	{
		//初日まで見た場合はそれ以前の日との差はないので0を返す
		return 0LL;
	}

	if (dp[day][num] != -1)
	{
		//既に調べた
		return dp[day][num];
	}
	ll cnt = 0;

	//day-1日目に何を着るかを調べる
	for (int i = 1; i <= N; i++)
	{
		//i番目の服を着る場合
		if (a[i] <= d[day - 1] && d[day - 1] <= b[i])
		{
			//i番目の服がday-1日目に着られる場合はi番目の服を着るとしてdfs
			//着られる温度条件を満たしている
			cnt = max(cnt, dfs(day - 1, i) + abs(c[num] - c[i]));
		}
	}
	return dp[day][num] = max(dp[day][num], cnt);
}

int main() {

	cin >> D >> N;

	d.push_back(-INF);
	a.push_back(-INF);
	b.push_back(-INF);
	c.push_back(-INF);
	//番兵を最初に埋め込む

	for (int i = 0; i < D; i++)
	{
		//D日
		int tmp;
		cin >> tmp;
		d.push_back(tmp);
	}

	for (int i = 0; i < N; i++)
	{
		//N種類の服
		int aa, bb, cc;
		cin >> aa >> bb >> cc;
		a.push_back(aa);
		b.push_back(bb);
		c.push_back(cc);
	}

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

	ll maxi = 0;
	for (int i = 1; i <= N; i++)
	{
		//D日目に服iを着る場合
		if (a[i] <= d[D] && d[D] <= b[i])
		{
			maxi = max(maxi, dfs(D, i));
		}
	}
	cout << maxi << endl;


	return 0;
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <cstdio>
using ll = long long;
using namespace std;

int T[210];
int A[210], B[210], C[210];
int dp[210][210];
int main(void)
{
    int D, N; //Dは服の計画を立てる日数 Nは服の種類の数
    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]; //A度以上B度以下 おしゃれ度C

    for (int i = 0; i < 210; ++i)
        for (int j = 0; j < 210; ++j)
            dp[i][j] = -1;
    //先に温度を考慮して分類しておく
    for (int i = 0; i < N; ++i)
    {
        if (T[0] >= A[i] && T[0] <= B[i])
            dp[0][i] = 0;
    }

    for (int i = 1; i < D; ++i)
    {
        for (int j = 0; j < N; ++j)
        { //服の番号
            for (int k = 0; k < N; ++k)
            {
                if (A[k] <= T[i] && B[k] >= T[i] && dp[i - 1][j] != -1)
                {
                    dp[i][k] = max(dp[i][k], dp[i - 1][j] + abs(C[j] - C[k]));
                }
            }
        }
    }

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

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

C++: #include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
	int a[201][201];
	int i2,i,n, m,o[300], x[300], y[300], z[300],i3;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; i++)
		scanf("%d", &o[i]);
	for (i = 1; i <= m; i++)
		scanf("%d %d %d", &x[i], &y[i], &z[i]);
	for (i = 0; i <= n; i++)
	for (i2 = 0; i2 <= m; i2++)
		a[i][i2] = -1;
	for (i = 1; i <= m; i++){
		if (o[1] >= x[i] && o[1] <= y[i]){
			a[1][i] = 0;
		}	
	}

	for (i = 1; i <= n; i++){
		for (i2 = 1; i2 <= m; i2++){
			if (a[i][i2] >= 0){
				for (i3 = 1; i3 <= m; i3++){
					if (o[i + 1] >= x[i3] && o[i + 1] <= y[i3])
						a[i + 1][i3] = max(a[i][i2] + abs(z[i2] - z[i3]), a[i + 1][i3]);


				}
			}
		}
	}
		/*for (i = 1; i <= n; i++){
			for (i2 = 1; i2 <= m; i2++){
				printf("%3d", a[i][i2]);
			}
			printf("\n");
		}*/
		int ma = 0;
		for (i = 1; i <= m; i++){
			if (a[n][i] > ma)
				ma = a[n][i];
		}
		printf("%d\n", ma);
	
}

C++: 
#include<iostream>

using namespace std;

int d,n;
int tenki[202];
int saiko[101],saitei[101];
int hade[101];
int dp[201][101];

int main(){
	cin>>d>>n;
	for(int i=0;i<d;i++){
		cin>>tenki[i];
	}
	for(int i=0;i<n;i++){
		cin>>saitei[i]>>saiko[i]>>hade[i];
	}
	for(int i=0;i<d;i++){
		for(int j=0;j<n;j++){
			if(i==0){
				dp[i][j]=0;
			}else{
				if(saitei[j]<=tenki[i]&&tenki[i]<=saiko[j]){
					int A=0;
					for(int k=0;k<n;k++){
						if(saitei[k]<=tenki[i-1]&&tenki[i-1]<=saiko[k]){
							A=max(A,dp[i-1][k]+abs(hade[k]-hade[j]));
						}
					}
					dp[i][j]=A;
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<n;i++){
		ans=max(ans,dp[d-1][i]);
	}
	cout<<ans<<endl;
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int dp[250][150],T[250],x[250][3],D,N,MAX;
main(){memset(dp,-99999,sizeof(dp));
    cin>>D>>N;
    for(int i=1;i<=D;i++){cin>>T[i];}
    for(int i=1;i<=N;i++){
        cin>>x[i][0]>>x[i][1]>>x[i][2];
        if(T[1]>=x[i][0] && T[1]<=x[i][1]){dp[1][x[i][2]]=0;}
    }
    for(int i=2;i<=D;i++){
        for(int j=1;j<=N;j++){
            if(T[i]>=x[j][0] && T[i]<=x[j][1]){
                for(int k=0;k<=100;k++){
                    dp[i][x[j][2]]=max(dp[i][x[j][2]],dp[i-1][k]+abs(x[j][2]-k));
                }
            }
        }
    }
    for(int i=0;i<=100;i++){MAX=max(MAX,dp[D][i]);}
    cout<<MAX<<endl;
    return 0;
}

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