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++: //AOJ 0579: Hot days
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, int> P;
const int MAX_N = 100, INF = 10000000;
int n, d, ans, c[200][61], save[3], dt[200], plan[200][2], s[200][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 - 1){
		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 = 0; 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 = 0; i<d; i++){
		plan[i][0] = INF;
	}
	for (int i = 0; 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[1][0] - plan[0][j]), 1));
		que.push(P(abs(plan[1][1] - plan[0][j]), 1 + INF));
	}
	p = que.top();
	solve(p.first, p.second, 0);
	cout << s[d - 1][save2] << endl;
	return 0;
}

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

const int INF = 1e+8;
const int MAX_D = 201;
const int MAX_N = 201;

int D, N, T[MAX_D], A[MAX_N], B[MAX_N], C[MAX_N];

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];
	
	// dp[d][k] := d日目で前の日に服kを着た時の派手さの差の絶対値の合計
	int dp[MAX_D][MAX_N];
	for(int d=0 ; d < D ; d++ ) fill(dp[d], dp[d] + MAX_N, -INF);
	for(int i=0 ; i < N ; i++ ){
		if( A[i] <= T[0] && T[0] <= B[i] ){
			for(int j=0 ; j < N ; j++ ){
				if( A[j] <= T[1] && T[1] <= B[j] ){
					dp[0][j] = abs(C[i] - C[j]);
				}
			}
		}
	}
	for(int d=0 ; d < D ; d++ ){
		for(int i=0 ; i < N ; i++ ){
			if( dp[d][i] == INF ) continue;
			
			for(int j=0 ; j < N ; j++ ){
				if( A[j] <= T[d+1] && T[d+1] <= B[j] ){
					dp[d+1][j] = min(dp[d+1][j], dp[d][i] + abs(C[i] - C[j]));
				}
			}
		}
	}
	int ans = -INF;
	for(int i=0 ; i < N ; i++ ){
		ans = min(ans, dp[D-1][i]);
	}
	cout << ans << endl;
}

C++: #include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

struct Tshirt{
	int a;
	int b;
	int c;
};

int solve(int,struct Tshirt);

int d,n;
int t[201];
int memo[210][210];
struct Tshirt data[201];

int main(){
	cin >> d >> n;
	for(int i=1;i<=d;i++){
		cin >> t[i];
	}
	for(int i=1;i<=n;i++){
		cin >> data[i].a;
		cin >> data[i].b;
		cin >> data[i].c;
	}
	int ans = 0;
	for(int i=1;i<=n;i++){
		if(t[1] >= data[i].a && t[1] <= data[i].b){
			int new_ans=0;
			new_ans = solve(2,data[i]);
			ans = max(ans,new_ans);
		}
	}

	cout << ans  << endl;
	return 0;
}
int solve(int day,struct Tshirt a){
	int rec = 0;
	if(memo[day][a.c] != 0)return memo[day][a.c];
	if(day == d){
		rec = 0;
	}
	for(int i=1;i<=n;i++){
		int o;
		if(t[day] >= data[i].a && t[day] <= data[i].b){
			o = abs(a.c-data[i].c);
			o += solve(day+1,data[i]);
			rec = max(rec,o);
		}
	}	
	memo[day][a.c] = rec;
	return rec;
}

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

using namespace std;

int d,n;
int ans;
int t[203],h[203][3];
int dp[203][203];
int main(){
	cin >> d >> n;
	for(int i = 1;i <= d;i++){
		cin >> t[i];
	}
	for(int i = 1;i <= n;i++){
		for(int j = 0;j < 3;j++){
			cin >> h[i][j];
		}
	}

	for(int i = 2;i <= d;i++){
		for(int j = 1;j <= n;j++){
			if(h[j][0] > t[i] || h[j][1] < t[i])continue;
			for(int k = 1;k <= n;k++){
				if(h[k][0] > t[i-1] || h[k][1] < t[i-1])continue;
				dp[i][j] = max(dp[i][j],dp[i-1][k]+abs(h[k][2]-h[j][2]));
			}
			ans = max(ans,dp[i][j]);
		}
	}
	cout << ans << endl;
	return 0;
}

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

#define pb(n) push_back(n)
#define fi first
#define se second
#define X real()
#define Y imag()
#define value(x,y,w,h) (x >= 0 && x < w && y >= 0 && y < h)
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

typedef long long ll ;
typedef deque<int> di ;
typedef deque<ll> dl ;
typedef map<string,int> dict;
typedef complex<double> comd;
typedef pair<int,int> pii;

constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0};
const int dx[] = {0,-1,0,1};

double CalcDist(comd p1, comd p2){
  return sqrt(pow(p1.X - p2.X,2.0) + pow(p1.Y -p2.Y,2.0));
}

template <typename T>
void out(deque < T > d)
{
  for(size_t i = 0; i < d.size(); i++)
  {
    debug(d[i]);
  }
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

int dp[2][200];
vector<int> day[220];
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N,D;
  cin >> N >> D;
  vector<int> d(N),a(D),b(D),c(D);
  rep(i,N){
    cin >> d[i];
  }
  rep(i,D){
    cin >> a[i] >> b[i] >> c[i];
  }
  rep(j,N){
    int u = 0;
    rep(i,D){
      if(a[i] <= d[j] && d[j] <= b[i]){
        ++u;
        day[j].pb(c[i]);
//         debug(day[j].size());
      }
    }
    sort(all(day[j]));
  }
//   rep(j,N){
//     rep(i,day[j].size()){
//       cout << day[j][i] << " " ;
//     }
//     cout << endl;
//   }
  int ans = 0;
  REP(i,0,N-1){
    int lm = 0,hm = 0;
    // ???????????????????????????
    int a,b,c,d;
    lm = abs(day[i][0]-day[i+1][0]);
    a = dp[0][i] + lm;
    //????????????????????§??????
    lm = abs(day[i][0]-day[i+1][day[i+1].size()-1]);
    b = dp[0][i]+ lm;
    //?????§?????????????????????
    hm = abs(day[i][day[i].size()-1]-day[i+1][0]);
    c = dp[1][i] + hm;
    //?????§?????????????????????
    hm = abs(day[i][day[i].size()-1]-day[i+1][day[i+1].size()-1]) ;
    d = dp[1][i] +hm;
    dp[0][i+1] = max(a,c);
    dp[1][i+1] = max(b,d);
  }
  cout << max(dp[0][N-1],dp[1][N-1]) << endl;
  return 0;
}