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>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int d,n,t[200],a[200],b[200],c[200];
int dp[201][200];

int main(){
	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++)
		for(int j=0;j<n;j++) dp[i][j]=-1;
	for(int i=0;i<n;i++) if(t[0]>=a[i]&&b[i]>=t[0]) dp[0][i]=0;
	for(int i=0;i<d-1;i++){
		for(int j=0;j<n;j++){
			if(dp[i][j]>=0) for(int k=0;k<n;k++) if(t[i+1]>=a[k]&&b[k]>=t[i+1]){
				dp[i+1][k]=max(dp[i][j]+abs(c[j]-c[k]),dp[i+1][k]);
			}
		}
	}
	int res=0;
	for(int i=0;i<n;i++) res=max(res,dp[d-1][i]);
	printf("%d\n",res);
}

C++: #include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int D, N, T[212], A[212], B[212], C[212];
int memo[212][212], ans;

int dp(int d, int b)
{
	if (memo[d][b] != -1) { return memo[d][b]; }
	if (d == 0) { return memo[d][b] = 0; }
	int res = 0;
	rep(i, N)
	{
		if (A[i] <= T[d - 1] && T[d - 1] <= B[i])
		{
			memo[d - 1][i] = dp(d - 1, i) + abs(C[b] - C[i]);
			if (d == D) { memo[d - 1][i] -= abs(C[b] - C[i]); }
			res = std::max(res, memo[d - 1][i]);
		}
	}
	return memo[d][b] = res;
}

int main()
{
	memset(memo, -1, sizeof(memo));
	in >> D >> N;
	rep(i, D) { in >> T[i]; }
	rep(i, N) { in >> A[i] >> B[i] >> C[i]; }

	rep(i, N)
	{
		if (A[i] <= T[D - 1] && T[D - 1] <= B[i]) { ans = std::max(ans, dp(D, i)); }
	}

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

C++: #include <bits/stdc++.h>

using namespace std;

typedef struct {
	int a, b, c;
} fuku_t;

int d, n;

int t[200];
fuku_t fuku[200];

int dp[200][200];

int main()
{
	cin >> d >> n;

	for (int i = 0; i < d; ++i) cin >> t[i];

	for (int i = 0; i < n; ++i) scanf("%d %d %d", &fuku[i].a, &fuku[i].b, &fuku[i].c);

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

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

	int ans = 0;

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

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

C++: #include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int solve(int hi,int cs);
int d,n;
int t[1000];
int ta[1111],tb[1111],c[1111];
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++: #include <iostream>
#include <stdio.h>
#include <string.h>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <algorithm>
#include <time.h>
#include <stdlib.h>

using namespace std;

int main (void)
{
	long Z[100][100],ZZ,n,m,a[100],b[100],c[100],d[100],huk[100][100],P;
	P = 0;

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for (int j = 0; j < m; j++)
	{
		cin >> b[j] >> c[j] >> d[j];
	}
	
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (b[j] <= a[i] && a[i] <= c[j])
			{
				huk[i][j] = d[j];
			}
			else
			{
				huk[i][j] = 0;
			}
		}
	}

	ZZ = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			P = 0;
			if (j != m)
			{
			P = huk[i][j] - huk[i + 1][j + 1];
			}
			if (P < 0)
			{
				P = P - P - P;
			}

			Z[i][j] = 0;
			Z[i][j] += P;

			if (Z[i][j] < ZZ)
			{
				ZZ = 0;
				ZZ = Z[100][100];
			}
		}
	}

	cout << Z << 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[MAX_N],B[MAX_N],C[MAX_N];
};

int N,D;
LL res=-INF;
LL Day[MAX_N];
LL mem[250][150];
clothes T;

LL cal(LL day,LL p,LL pp,LL sum){
        if(!mem[day][p]){
            res=mem[day][p];
        }
        else{
            if(res<sum+abs(pp-p)){
                mem[day][p]=res=sum+abs(pp-p);
                //cout<<"hoge"<<endl;
            }
            if(day==N+1)return 0;
            else{
            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 mem[day][p]=res;
}


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

C++: #include<iostream>

using namespace std;

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

int Abs(int n){
	return n>0?n:n*-1;
}

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<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < n ; ++i)
int t[200],a[200],b[200],c[200],dp[201][201],D,N;
int solve(int today,int yd){ //今日の日付, 昨日の服の番号
  if(today == D) return 0;
  if(dp[today][yd]) return dp[today][yd];
  int res = 0;
  for(int i = 0 ; i < N ; i++ ){
    if( t[today] >= a[i] && t[today] <= b[i] ){
      res = max(res,solve(today+1,i) + (today?abs(c[i]-c[yd]):0));
    }
  }
  return dp[today][yd] = res;
}
int main(){
  cin >> D >> N;
  rep(i,D) cin >> t[i];
  rep(i,N) cin >> a[i] >> b[i] >> c[i];
  cout << solve(0,0) << endl;
}