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 <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

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

int dfs(int day, int b) {
  if (day == D) return 0;
  if (memo[day][b] != -1) return memo[day][b];

  int &res = memo[day][b];
  for (int i = 0; i < N; ++i) {
    if (A[i] <= T[day] && T[day] <= B[i]) {
      res = max(res, dfs(day + 1, C[i]) + abs(b - C[i]));
    }
  }

  return res;
}

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];
  memset(memo, -1, sizeof(memo));

  int ans = 0;
  for (int i = 0; i < N; ++i) {
    if (A[i] <= T[0] && T[0] <= B[i]) {
      ans = max(ans, dfs(1, C[i]));
    }
  }
  cout << ans << endl;

  return 0;
}

C++: #include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n;i>=0;i--)
#define INF 100000005
#define MAX 100000001
#define dmp make_pair
#define dpb push_back
#define fi first
#define se second
using namespace std;
//__gcd(a,b), __builtin_popcount(a);

int a[201], b[201][3];
pair<int,int> dp[201][2];
int main(){
	int d, n, ans = 0;
	scanf("%d%d", &d, &n);
	rrep(i,d)scanf("%d", &a[i]);
	rrep(i,n)scanf("%d%d%d", &b[i][0], &b[i][1], &b[i][2]);
	int t1, t2, x, y;
	for(int i = 1;i <= d;i++){
		t1 = INF;t2 = 0;
		for(int j = 1;j <= n;j++){
			if(b[j][0] <= a[i] && a[i] <= b[j][1]){
				t1 = min(t1, b[j][2]);
				t2 = max(t2, b[j][2]);
			}
		}
		dp[i][0].se = t1;
		dp[i][1].se = t2;
		x = dp[i-1][0].se;
		y = dp[i-1][1].se;
		dp[i][0].fi = max(dp[i-1][1].fi + abs(y-t1), dp[i-1][0].fi + abs(x-t1));
		dp[i][1].fi = max(dp[i-1][0].fi + abs(x-t2), dp[i-1][1].fi + abs(y-t2));
		if(i == 1){
			dp[i][0].fi = 0;
			dp[i][1].fi = 0;
		}
	}
	t1 = dp[d][0].fi;
	t2 = dp[d][1].fi;
	printf("%d\n", max(t1, t2));
	return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <iomanip>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define All(v) (v).begin(),(v).end()
typedef long long ll;

int dp[210][210];

int main(){
    int D,N;
    cin >> D >> N;
    vector<int> T(D);
    rep(i,D){
        cin >> T[i];
    }
    vector<int> A(N),B(N),C(N);
    rep(i,N){
        cin >> A[i] >> B[i] >> C[i];
    }

    rep(i,110)rep(j,210)dp[i][j]=-1;
    rep(i,N)if(A[i]<=T[0]&&T[0]<=B[i])dp[1][i]=0;

    for(int i=2;i<=D;i++){
        for(int j=0;j<N;j++){
            if(A[j]<=T[i-1]&&T[i-1]<=B[j])
                for(int k=0;k<N;k++){
                    if(dp[i-1][k]==-1)continue;
                    dp[i][j]=max(dp[i][j],dp[i-1][k]+abs(C[j]-C[k]));
                }
            else dp[i][j]=-1;
        }
    }
    int res = 0;
    rep(i,N){
        res = max(res,dp[D][i]);
    }
    cout << res << endl;
    return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int dp[250][150],T[250],x[250][3],D,N,MAX;
main(){memset(dp,-1000000,sizeof(dp));
    cin>>D>>N;
    for(int i=1;i<=D;i++){cin>>T[i];}
    for(int i=1;i<=N;i++){
        cin>>x[i][0]>>x[i][1]>>x[i][2];
        if(T[1]>=x[i][0] && T[1]<=x[i][1]){dp[1][x[i][2]]=0;}
    }
    for(int i=2;i<=D;i++){
        for(int j=1;j<=N;j++){
            if(T[i]>=x[j][0] && T[i]<=x[j][1]){
                for(int k=0;k<=100;k++){
                    dp[i][x[j][2]]=max(dp[i][x[j][2]],dp[i-1][k]+abs(x[j][2]-k));
                }
            }
        }
    }
    for(int i=0;i<=100;i++){MAX=max(MAX,dp[D][i]);}
    cout<<MAX<<endl;
    return 0;
}

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

int d, n;
int t[210];
int a[210], b[210], c[210];
int dp[210][210];
int main()
{
  cin >> d >> n;
  for(int i = 1; i <= d; i++)
    cin >> t[i];
  for(int i = 1; i <= n; i++)
    cin >> a[i] >> b[i] >> c[i];

  memset(dp, -1, sizeof dp);
  for(int i = 1; i <= n; i++)
    if(a[i] <= t[1] && t[1] <= b[i])
      dp[1][i] = 0;

  for(int i = 1; i <= d - 1; i++)
    for(int j = 1; j <= n; j++)
      if(dp[i][j] != -1)
	for(int k = 1; k <= n; k++)
	  if(a[k] <= t[i + 1] && t[i + 1] <= b[k])
	    dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + abs(c[j] - c[k]));

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

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

C++: #include <iostream>
#include <fstream>
#include <math.h>

using namespace std;
int T[200], A[200], B[200], C[200], D, N;
int Cs[200][200], CsNumber[200], valueCs[200][200];

inline void readinput(){
//	ifstream fin("input_2012_4.dat");
	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];
}

inline void output_2d(int X[200][200]){
	for(int i=0; i<D; i++){
		for(int j=0; j<N; j++){
			cout << X[i][j];
			if(j != N-1) cout << " ";
			else cout << endl;
		}
	}
}

inline void putCs(){
	int idx;
	for(int i=0; i<D; i++){
		idx = 0;
		for(int j=0; j<N; j++){
			if(A[j]<=T[i] && T[i]<=B[j]){
				Cs[i][idx] = C[j];
				idx += 1;
			}
		CsNumber[i] = idx;
		}
	}
}

inline int solver(){
	int max, maxidx, buf;
	
	//initialize
	for(int i=0; i<200; i++){
		for(int j=0; j<200; j++) valueCs[i][j] = 0;
	}
	
	for(int i=D-1; i>0; i--){	// D-1 to 1
		for(int j1=0; j1<CsNumber[i-1]; j1++){
			max = 0;
			for(int j2=0; j2<CsNumber[i]; j2++){
				buf = fabs(Cs[i-1][j1] - Cs[i][j2]) + valueCs[i][j2];
				if(max < buf){
					max = buf;
					maxidx = j2;
				}
			}
			valueCs[i-1][j1] += max;
		}
	}
	max = 0;
	for (int j=0; j<CsNumber[0]; j++){
		buf = valueCs[0][j];
		if(max < buf) max = buf;
	}
	return max;
}

int main(){
	readinput();
	putCs();
	cout << solver() << endl;
//	cout << "--- Cs ---" << endl;
//	output_2d(Cs);
//	cout << "--- valueCs ---" << endl;
//	output_2d(valueCs);
	return 0;
}

C++: #include <cstdio>
#include <algorithm>

using namespace std;

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

int d, n;

int t[200];
fuku_t f[200];

int dp[200][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", &f[i].a, &f[i].b, &f[i].c);

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

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

	int ans = 0;

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

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