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 <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<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
#define INF (-1 * (1 << 29))
using namespace std;

struct Clothes{
    int low, up, glitz;
};

int dp[205][205];
int d, n, t[205];
Clothes c[205];

void update(int day, int before, int now){
    if(c[now].low <= t[day] && c[now].up >= t[day]){
        if(day == 0) dp[day][now] = 0; //テ・ツ按敕ヲツ猟・テ」ツ?ォテァツ敖?」ツつ凝ヲツ慊?
        else if(dp[day - 1][before] != INF){
            dp[day][now] = max(dp[day][now], dp[day - 1][before] + abs(c[before].glitz - c[now].glitz)); 
        }
    }
}

int solve(){
    rep(day,d){
        rep(before,n){
            rep(now,n){
                update(day, before, now);
            }
        }
    }

/*
    rep(i,d){
        rep(j,n){
            cout << dp[i][j] << ' ';
        }
        cout << endl;
    }
*/

    int retval = -1;
    rep(i,n){
        if(dp[d - 1][i] == INF) continue;
        retval = max(retval, dp[d - 1][i]);
    }
    return retval;
}

int main(){
    rep(i,105) rep(j,105) dp[i][j] = INF;
    cin >> d >> n;
    rep(i,d) cin >> t[i];
    rep(i,n) cin >> c[i].low >> c[i].up >> c[i].glitz;
    cout << solve() << endl;
}

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

int temp[201];
int a[201], b[201], c[201];

int dp[101][201];

int main() {
  int D,N;
  cin>>D>>N;
  for (int i=0; i<D; ++i) cin>>temp[i];
  for (int i=0; i<N; ++i) cin>>a[i]>>b[i]>>c[i];

  for (int i=0; i<D; ++i)
    for (int j=0; j<201; ++j)
      dp[i][j] = 1<<29;

  for (int i=0; i<N; ++i) {
    if (temp[0] <= b[i] && a[i] <= temp[0])
      dp[0][c[i]] = 0;
  }

  for (int i=1; i<D; ++i) {
    for (int j=0; j<N; ++j) {
      if (temp[i] <= b[j] && a[j] <= temp[i]) {
        for (int k=0; k<201; ++k) {
          if (dp[i-1][k] == 1<<29) continue;
          if (dp[i][c[j]] == 1<<29)  dp[i][c[j]] = dp[i-1][k]+abs(k-c[j]);
          dp[i][c[j]] = max(dp[i-1][k]+abs(k-c[j]), dp[i][c[j]]);
        }
      }
    }
  }

  int ans = 0;
  for (int i=0; i<201; ++i) {
    if (dp[D-1][i] == 1<<29) continue;
    ans = max(ans, dp[D-1][i]);
  }
  cout<<ans<<endl;
}

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

#include <bits/stdc++.h>

using namespace std;
#define ll long long

#define rep(i, a) for (int i = 0; (i) < (int) (a); (i)++)
#define reps(i, a, b) for (int (i) = (int) (a); (i) < (int) (b); (i)++)
#define rrep(i, a) for (int (i) = (int) a-1; (i) >= 0; (i)--)
#define rreps(i, a, b) for (int (i) = (int) (a)-1; (i) >= (int) (b); (i)--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define TRUE__ "yes"
#define FALSE__ "no"
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x

#define INF 1e9

int dp[201][101];
int temp[200];
vector<pair<pair<int, int>, int> > v;

int D, N;

void init()
{
	rep(i, 201) rep(j, 101) dp[i][j] = -INF;
	dp[0][0] = 0;
}
	

int main()
{
	init();
	cin >> D >> N;
	rep(i, D) cin >> temp[i];
	rep(i, N) {
		CIN(int, t);
		CIN(int, tt);
		CIN(int, ttt);
		v.PB(MP(MP(t, tt), ttt));
	}
	sort(all(v));
	rep(i, D) {
		int t = temp[i];
		vector<int> vv; 
		rep(j, v.size()) {
			auto pt = v[j];
			auto ptt = pt.first;
			if (ptt.first <= t && ptt.second >= t) {
				vv.PB(pt.second);
			}
		}
		rep(j, 101) {
			if (dp[i][j] == -INF) continue;
			rep(k, vv.size()) {
				if (i == 0) {
					dp[i+1][vv[k]] = 0;
				} else {
					dp[i+1][vv[k]] = max(dp[i+1][vv[k]], dp[i][j] + abs(j-vv[k]));
				}
			}
		}	
	}
	int res = -1;
	rep(i, 101) res = max(res, dp[D][i]);
	cout << res << endl;
}

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

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

int D, N;
int T[201];
int A[201],B[201],C[201];
bool suit[201][201];
int dp[201][201];

int main() {
    int i, j, k;
    
    scanf("%d%d", &D, &N);
    for (i = 0; i < D; ++i) {
        scanf("%d", &T[i]);
    }
    for (j = 0; j < N; ++j) {
        scanf("%d%d%d", &A[j], &B[j], &C[j]);
    }
    
    for (i = 0; i < D; ++i) for (j = 0; j < N; ++j) {
        suit[i][j] = (A[j] <= T[i] && T[i] <= B[j]);
    }
    
    for (i = 0; i < D; ++i) for (j = 0; j < N; ++j) {
        //	-1 : impossible
        dp[i][j] = -1;
    }
    for (j = 0; j < N; ++j) if (suit[0][j]) {
        dp[0][j] = 0;
    }
    for (i = 0; i < D - 1; ++i){
        for (j = 0; j < N; ++j){
            if (dp[i][j] >= 0) {
                for (k = 0; k < N; ++k) if (suit[i + 1][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]);
                        cout << "dp[" << i+1 << "][" << k << "] = " <<
                        dp[i+1][k] << endl;
                    }
                }
            }
        }
    }
    
    int ans = -1;
    for (j = 0; j < N; ++j) {
        if (ans < dp[D - 1][j]) {
            ans = dp[D - 1][j];
        }
    }
    printf("%d\n", ans);
    
    return 0;
}