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;

typedef struct {
	int a;
	int b;
	int 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) for (int j = 0; j < n; ++j) {
		if (fuku[j].a <= t[0] && t[0] <= fuku[j].b && fuku[i].a <= t[1] && t[1] <= fuku[i].b) {
			dp[1][i] = max(dp[1][i], abs(fuku[j].c - fuku[i].c));
		}
	}

	for (int i = 2; i < d; ++i) for (int j = 0; j < n; ++j) for (int k = 0; k < n; ++k) {
		if (fuku[j].a <= t[i] && t[i] <= fuku[j].b && 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++: //AOJ 0579: Hot days
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, int> P;
const int INF = 10000000;
int n, d, ans, c[201][61], save[3], dt[201], plan[201][2], s[201][101], save2;
priority_queue<P> que;
P p;
void solve(int a, int day, int b){
	int jud = day / INF;
	day = day % INF;
	s[day][plan[day][jud]] = max(a + s[day - 1][plan[day - 1][b]], s[day][plan[day][jud]]);
	if (day == d){
		save2 = plan[day][jud];
		return;
	}
	que.push(P(abs(plan[day + 1][0] - plan[day][jud]), day + 1));
	que.push(P(abs(plan[day + 1][1] - plan[day][jud]), day + 1 + INF));
	p = que.top();
	que.pop();
	solve(p.first, p.second, jud);
}
int main(){
	cin >> d >> n;
	for (int i = 1; i <= d; i++){
		cin >> dt[i];
	}
	for (int i = 0; i<n; i++){
		for (int j = 0; j<61; j++){
			c[i][j] = -1;
		}
	}
	for (int i = 0; i < n; i++){
		cin >> save[0] >> save[1] >> save[2];
		for (int j = save[0]; j <= save[1]; j++){
			c[i][j] = save[2];
		}
	}
	for (int i = 1; i<=d; i++){
		plan[i][0] = INF;
	}
	for (int i = 1; i <= d; i++){
		for (int j = 0; j < n; j++){
			if (c[j][dt[i]] != -1){
				plan[i][0] = min(c[j][dt[i]], plan[i][0]);
				plan[i][1] = max(c[j][dt[i]], plan[i][1]);
			}
		}
	}
	for (int j = 0; j <= 1; j++){
		que.push(P(abs(plan[2][0] - plan[1][j]), 2));
		que.push(P(abs(plan[2][1] - plan[1][j]), 2 + INF));
	}
	p = que.top();
	que.pop();
	solve(p.first, p.second, 0);
	cout << s[d][save2] << endl;
	return 0;
}

C++: #include<iostream>
#include<math.h>
using namespace std;
int solve(int hi,int cs);
int d,n;
int t[100];
int ta[111],tb[111],c[111];
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<algorithm>
using namespace std;
int main() {
	long long n, a, b, c, d, e, sum = 0, num = 0; cin >> n >> a;
	long long test[201] = { 0 }, dp[201] = { 0 }, dpp[201] = { 0 };
	long long cc[201] = { 0 }, dd[201] = { 0 }, ee[201] = { 0 };
	for (int h = 0; h < n; h++) {
		cin >> b; test[h] = b;
	}
	for (int h = 0; h < a; h++) {
		cin >> c >> d >> e;
		cc[h] = c; dd[h] = d; ee[h] = e;
	}
	for (int h = 0; h < n; h++) {
		long long ma = 0, mi = 100000;
		for (int i = 0; i < a; i++) {
			if (cc[i] <= test[h] && test[h] <= dd[i]) {
				ma = max(ma, ee[i]);
				mi = min(mi, ee[i]);
			}
		}
		dp[h] = ma; dpp[h] = mi;
	}
	long long su[201] = { 0 }, nu[201] = { 0 };
	//su[0] = dp[0]; nu[0] = dpp[0];
	for (int h = 1; h < n; h++) {
		su[h] = max(abs(dp[h - 1] - dp[h]) + su[h - 1], abs(dpp[h - 1] - dp[h]) + nu[h - 1]);
		nu[h] = max(abs(dp[h - 1] - dpp[h]) + su[h - 1], abs(dpp[h - 1] - dpp[h]) + nu[h - 1]);
		//cout << su[h] << ' ' << nu[h] << endl;
	}
	cout << max(su[n - 1], nu[n - 1]) << endl;
	cin >> n;
}

C++: #pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define UNIQUE(v) { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); }
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return true;} return false; }
template<class T> bool chmin(T &a, const T &b) {if (a > b) {a = b; return true;} return false; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) (q ? "Yes" : "No")
#define YES(q) (q ? "YES" : "NO")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) { cerr << "[DEBUG] " #q ": ["; REP(dumpall_i, (q).size()) { cerr << q[dumpall_i] << (dumpall_i == (q).size() - 1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; }
template<class T> T gcd(const T &a, const T &b) { return a < b ? gcd(b, a) : b ? gcd(b, a % b) : a; }
template<class T> T lcm(const T &a, const T &b) { return a / gcd(a, b) * b; }

// gcc拡張マクロ
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
using  ll = long long;
using ull = unsigned long long;
using  ld = long double;
using namespace std;

// モジュール

// 処理内容
int main() {
    
    ll d, n; cin >> d >> n;
    vector<ll> t(d), a(n), b(n), c(n);
    REP(i, d) cin >> t[i];
    REP(i, n) cin >> a[i] >> b[i] >> c[i];

    // dp[i][j] := i日目(0-indexed)までみて、i日目に服jを着たときのスコア最大値
    vector<vector<ll>> dp(d, vector<ll>(n, 0));
    RANGE(i, 1, d-1) {
        REP(j, n) {
            REP(j0, n) {
                if (a[j0] <= t[i-1] && t[i-1] <= b[j0] && a[j] <= t[i] && t[i] <= b[j]) {
                    chmax(dp[i][j], dp[i-1][j0] + abs(c[j] - c[j0]));
                }
            }
        }
    }

    cout << *max_element(ALL_OF(dp[d-1])) << endl;
    
}

C++: #include<iostream>
#include<cmath>
using namespace std;
int dp[201][201];
int t[201],u[201],v[201],w[201];
int N,D,ans=0;
int main(){
  cin>>N>>D;
  for(int i=1;i<=N;i++)cin>>t[i];
  for(int i=1;i<=D;i++){
    cin>>u[i]>>v[i]>>w[i];
    if(t[1]<u[i]||v[i]<t[1])dp[1][i]=-1;
    else dp[1][i]=0;
  }
  for(int i=2;i<=N;i++){
    for(int j=1;j<=D;j++){
      dp[i][j]=-1;
      if(t[i]<u[j]||v[j]<t[i])continue;
      for(int k=1;k<=D;k++){
	if(dp[i-1][k]==-1)continue;
	dp[i][j]=max(dp[i][j],dp[i-1][k]+abs(w[k]-w[j]));
      }
      ans=max(ans,dp[i][j]);
    }
  }
  cout<<ans<<endl;
  return 0;
}