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 <cctype>
#include <limits.h>
#include <math.h>
#include <complex>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <iostream>

#define VARIABLE(x) cerr << #x << "=" << x << endl
#define BINARY(x) static_cast<bitset<16> >(x);
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)
#define if_range(x, y, w, h) if (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))

const int INF = 1000000000;
const double EPS = 1e-8;
const double PI = 3.14159;
int dx[4]={-1, 0, 1, 0}, dy[4]={0, -1, 0, 1};
using namespace std;
typedef pair<int, int> P;

/** Problem0579 : Hot days **/
int D, N;
vector<int> T, A, B, C;
int dp[201][101];

int solve(int d, int old)
{
	if (d >= D) return 0;
	
	if (dp[d][old]>=0)
		return dp[d][old];
	
	int res=0;
	rep(i, N) {
		if (A[i] <= T[d] && T[d] <= B[i]) {
			int t = abs(C[i] - old) + solve(d+1, C[i]);
			res = max(res, t);
		}
	}
	
	return dp[d][old] = res;
}

int main()
{
	cin>>D>>N;
	T.resize(D);
	rep(i, D) cin>>T[i];
	A.resize(N); B.resize(N); C.resize(N);
	rep(i, N) {
		cin>>A[i]>>B[i]>>C[i];
	}
	memset(dp, -1, sizeof(dp));
	
	int ans=0;
	rep(i, N) {
		if (A[i] <= T[0] && T[0] <= B[i])
			ans = max(ans, solve(1, C[i]));
	}
	
	cout << ans << endl;
}

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

#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define repi(i,a,b) for(int i = (a); i < (b); i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
int dp[210][210];//dp[i][j]:=i+2日に服jを選んだ時の最大値
int t[210]={0};
int a[210],b[210],c[210];
int D,N;
int rec(int id,int cloth){
	if(id==D)return 0;
	if(dp[id][cloth]>=0)return dp[id][cloth];
	int tmp = 0;
	for(int i =0;i <N;i++){
		if(a[i]<=t[id]&&t[id]<=b[i]){
			tmp=max(tmp,rec(id+1,i)+abs(c[i]-c[cloth]));
		}
	}
	return dp[id][cloth]=tmp;
}

int main(){
	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];
	}
	int ans = 0;
	memset(dp, -1, sizeof(dp));
	for(int i =0;i <N;i++){
		if(a[i]<=t[0]&&t[0]<=b[i]){
			ans =max(ans,rec(1,i));
		}
	}
	cout <<ans<<endl;
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <cmath>
using namespace std;

int main() {
	int D, N;
	cin >> D >> N;
	vector<int> days(D);
	for_each(days.begin(), days.end(), [](int& x) {cin >> x; });
	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] <= days[1] && days[1] <= B[i]) {
			int tmp = 0;
			for (int j = 0; j < N; j++) {
				if (A[j] <= days[0] && days[0] <= B[j]) {
					if (tmp < abs(C[j] - C[i]))tmp = abs(C[j] - C[i]);
				}
			}
			dp[1][i] = tmp;
		}
	}

	for (int i = 1; i < D - 1; i++) {
		for (int j = 0; j < N; j++) {
			if (dp[i][j] == -1)continue;
			for (int k = 0; k < N; k++) {
				if (A[k] <= days[i + 1] && days[i + 1] <= B[k]) {
					if (dp[i + 1][k] < dp[i][j] + abs(C[j] - C[k]))dp[i + 1][k] = dp[i][j] + abs(C[j] - C[k]);
				}
			}
		}
	}

	int ans = 0;
	for (int i = 0; i < N; i++) {
		if (ans < dp[D - 1][i]) ans = dp[D - 1][i];
	}

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

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

int z(int x){
	if(x<0)return -x;
	return x;
}

int main(){
	int MINF=-100000000;
	int d,n,t[202],a[202],b[202],c[202],dp[202][202];
	for(int i=0;i<202;i++)for(int j=0;j<202;j++)dp[i][j]=MINF;
	scanf("%d%d",&d,&n);
	for(int i=1;i<=d;i++){
		scanf("%d",&t[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
	}
	for(int i=1;i<=n;i++)if(a[i]<=t[1]&&t[1]<=b[i])dp[1][i]=0;
	for(int i=2;i<=d;i++){
		for(int j=1;j<=n;j++){
			if(a[j]<=t[i]&&t[i]<=b[j]){
				for(int k=1;k<=n;k++){
					if(dp[i][j]<dp[i-1][k]+z(c[k]-c[j]))dp[i][j]=dp[i-1][k]+z(c[k]-c[j]);
				}
			}
		}
	}
	/*for(int i=1;i<=d;i++){
		cout<<i<<":"<<endl;
		for(int j=1;j<=n;j++){
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}*/
	int ans=MINF;
	for(int i=1;i<=n;i++){
		if(ans<dp[d][i])ans=dp[d][i];
	}
	printf("%d\n",ans);
}

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;
	if(score[d][k] >= e) return 0;
	score[d][k] = e;
	if(d == D) return score[d][k] = 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;
		int nexte = e + fabs(use.eva - kind[k].eva);
		if(d > 0)ret = max(ret, solve(d + 1, i, nexte));
		else ret = max(ret, solve(d + 1, i, e));
	}

	return ret;
}

int main(){
	fill_n(temp, 201, -1);
	fill_n(*score, 201 * 200, -1);
	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, 0) << endl;
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

struct uyu{int a, b, c;};

int d, n;
int t[202];
vector<uyu> po;

int dfs(int i, int cost, int front)
{
  int ret = 0;
  
  if (i == d) return cost;
  if (i == 0){
    for (auto &j : po){
      if (t[i] < j.a || j.b < t[i]) continue;
      ret = max(ret, dfs(i + 1, 0, j.c));
    }
    return ret;
  }

  for (auto &j :po){
    if (t[i] < j.a || j.b < t[i]) continue;
    ret = max(ret, dfs(i + 1, cost + abs(front - j.c), j.c));
  }

  return ret;
}

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

  for (int i = 0; i < n; i++){
    uyu s;
    cin >> s.a >> s.b >> s.c;
    po.push_back(s);
  }

  cout << dfs(0, 0, 0) << endl;
}