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 <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

typedef long long ll;

using namespace std;


int d,n,t[200],a[200],b[200],c[200],dp[201][200],ans;

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",&a[i],&b[i],&c[i]);
    
    for(int i=0;i<d-1;i++){
        for(int j=0;j<n;j++){
            if(a[j]<=t[i] && t[i]<=b[j]){
                for(int k=0;k<n;k++){
                    dp[i+1][k]=max(dp[i+1][k],dp[i][j]+abs(c[j]-c[k]));
                }
            }
        }
    }
    
    for(int i=0;i<n;i++)
        if(a[i]<=t[d-1] && t[d-1]<=b[i])
            ans=max(ans,dp[d-1][i]);
    
    printf("%d\n",ans);
    
    
    return 0;
}

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

#define lint long long
#define P pair<int, int>
#define LLP pair<long long, long long>
#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)
#define repr(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())

const int IINF = (1 << 30) - 1;
const long long LLINF = 1LL << 61;
const long long MOD = 1000000007LL;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

template<typename T>
bool chmax(T &a, T b){
    if(a < b){
        a = b;
        return true;
    }else{
        return false;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int d, n;
    cin >> d >> n;

    vector<int> t(d);
    rep(i, d){
        cin >> t[i];
    }

    vector<int> c(n);
    vector< vector<bool> > v(d, vector<bool>(n, false));
    rep(i, n){
        int a, b;
        cin >> a >> b >> c[i];
        rep(j, d){
            if(a <= t[j] && t[j] <= b){
                v[j][i] = true;
            }
        }
    }

    int dp[201][200] = {0};
    REP(i, 1, d){
        rep(j, n){
            rep(k, n){
                if(v[i - 1][j] && v[i][k]){
                    chmax(dp[i + 1][k], dp[i][j] + abs(c[j] - c[k]));
                }
            }
        }
    }

    int ans = 0;
    rep(j, n){
        chmax(ans, dp[d][j]);
    }

    cout << ans << endl;

    return 0;
}

C++: #include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<cmath>
using namespace std;
#define fr first
#define sc second
#define MAX 201
int main(){
  int D,N,T[MAX],A[MAX],B[MAX],C[MAX],dp[MAX][MAX];
  bool can[MAX][MAX];
  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];
  }
  for(int i = 0 ; i < D ; i++ ){
    for(int j = 0 ; j < N ; j++ ){
      can[i][j] = ( A[j] <= T[i] && T[i] <= B[j] );
      dp[i][j] = -1;
    }
  }
  for(int i = 0 ; i < N ; i++){
    if(can[0][i]) dp[0][i] = 0;
  }
  for(int i = 0 ; i < D - 1 ; i++)
    for(int j = 0 ; j < N ; j++)
      if(dp[i][j] != -1)
        for(int k = 0 ; k < N ; k++){
          if(can[i+1][k]){
            dp[i+1][k] = max(dp[i+1][k],dp[i][j] + abs( C[j] - C[k] ));
          }
        }

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

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

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define MP make_pair

typedef pair<int, int> PII;

int d, n, mt[200];
PII clothes[200];
vector<PII> v;
int result[200];

int search(int tem, int di) {
  int ni, res = 0;
  if (di == 1) ni = 0;
  else ni = n - 1;

  while (0 <= ni && ni < d) {
    PII nc = clothes[v[ni].second];
    if (nc.first <= tem && nc.second >= tem) return res = v[ni].first;
    ni += di;
  }

  return 0;
}

int culc() {
  int res = 0;
  REP(i, d - 1) res += abs(result[i] - result[i+1]);
  return res;
}

int main() {
  cin >> d >> n;
  REP(i, d) scanf("%d", &mt[i]);
  v.resize(n);
  REP(i, n) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    clothes[i] = MP(a, b);
    v[i] = MP(c, i);
  }
  sort(v.begin(), v.end());

  int ans = -1;
  int di[] = {1, -1};
  REP(i, 2) {
    REP(j, d) result[j] = search(mt[j], di[(j+i)%2]);
    ans = max(ans, culc());
  }

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

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

	return score[d][k] = max(score[d][k], ret);
}

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

C++: #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define INF 1 << 30
#define EPS 1e-10

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int D, N, C[200], T[200], A[200], B[200], dp[200][200];

int dfs(int d, int prev){
  //  printf("%d %d\n", d, prev);
  if(d == D) return 0;
  if(dp[d][prev] >= 0) return dp[d][prev];

  int res = 0;
  rep(i, N){
    if(A[i] > T[d] || B[i] < T[d]) continue;
    res = max(res, dfs(d+1, i) + abs(C[i] - C[prev]));
  }
  return dp[d][prev] = res;
}

int main(){
  scanf("%d%d", &D, &N);
  rep(i, D) scanf("%d", T+i);
  rep(i, N) scanf("%d%d%d", A + i, B + i, C + i);
  memset(dp, -1, sizeof(dp));

  int res = 0;
  rep(i, N) if(A[i] <= T[0] && T[0] <= B[i]) res = max(res, dfs(1, i));
  printf("%d\n", res);
  return 0;
}