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>
#include<cmath>
using namespace std;
#define REP(i, b, e) for ( int i = b; i < (int)e; i++ )
#define rep(i, n) REP(i, 0, n)
static const int DMAX = 200;
static const int NMAX = 200;
static const int INPOS = -1;

main(){
  int D, N, T[DMAX+1], C[NMAX+1], dp[NMAX+1][DMAX+1];
  pair<int, int> AB[NMAX+1];
  cin >> D >> N;
  rep(i, D) cin >> T[i+1]; // +1 for 1 base
  rep(i, N) cin >> AB[i+1].first >> AB[i+1].second >> C[i+1];
  rep(i, N+1) rep(j, D+1) dp[i][j] = INPOS;
  
  REP(i, 1, N+1)
    if ( AB[i].first <= T[1] && T[1] <= AB[i].second ) dp[i][1] = 0;

  REP(j, 2, D+1){
    REP(i, 1, N+1){
      if ( !( AB[i].first <= T[j] && T[j] <= AB[i].second) ) continue;
      REP(k, 1, N+1){
	if ( dp[k][j-1] == INPOS ) continue;
	dp[i][j] = max(dp[i][j], dp[k][j-1] + abs(C[k] - C[i]));
      }
    }
  }

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

C++: #include <iostream>
#include <algorithm>
using namespace std;
int D, N, x[209], a[209], b[209], c[209], dp[209][209];
int main() {
	cin >> D >> N;
	for (int i = 0; i < D; i++) cin >> x[i];
	for (int i = 0; i < N; i++) cin >> a[i] >> b[i] >> c[i];
	for (int i = 1; i < D; i++) {
		for (int j = 0; j < N; j++) {
			if (!(a[j] <= x[i] && x[i] <= b[j])) continue;
			for (int k = 0; k < N; k++) {
				if (!(a[k] <= x[i - 1] && x[i - 1] <= b[k])) continue;
				dp[i][j] = max(dp[i][j], dp[i - 1][k] + abs(c[j] - c[k]));
			}
		}
	}
	cout << *max_element(dp[D - 1], dp[D - 1] + N) << endl;
	return 0;
}

C++: #include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
#include <set>

#define INF_LL 9000000000000000000
#define INF 2000000000

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

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

class Union_find{
private:
	vector<int> par;
	vector<int> rank;
	int n;

public:
	Union_find(int a){
		n = a;
		for(int i = 0;i < n;i++){
			par.push_back(i);
			rank.push_back(0);
		}
	}

	int find(int x){
		if(par[x] == x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;

		if(rank[x] < rank[y]){
			par[x] = y;
		}else{
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
		}
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}
};

int main(void){
	int D, N;
	int T[200];
	int dp[200][101];
	vector<int> C[61];
	cin >> D >> N;
	REP(i, D){
		cin >> T[i];
	}
	REP(i, N){
		int a, b, c;
		cin >> a >> b >> c;
		FOR(j, a, b+1){
			C[j].push_back(c);
		}
	}
	REP(i, 200){
		fill(dp[i], dp[i]+101, -1);
	}
	REP(i, C[T[0]].size()){
		dp[0][C[T[0]][i]] = 0;
	}
	FOR(i, 1, D){
		REP(j, C[T[i]].size()){
			int diff = 0;
			REP(k, 101){
				if(dp[i-1][k] == -1) continue;
				diff = max(diff, dp[i-1][k] + abs(C[T[i]][j] - k));
			}
			dp[i][C[T[i]][j]] = diff;
		}
	}
	ll res = 0;
	REP(i, 101){
		if(dp[D-1][i] != -1) res += dp[D-1][i];
	}
	cout << res << endl;
}

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

using namespace std;

int t[200];
int a[200], b[200], c[200];

int dp[200][200];

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

    int ans = 0;

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

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

C++: #include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

struct cloth{int a,b,c;};
const int MAX = 205;
vector<cloth> V;
vector<int> Temp;
int N,D,dp[MAX][MAX];

void input(){
  cin >> D >> N;
  Temp.resize(D);
  V.resize(N);
  for(int i = 0; i < D; i++) cin >> Temp[i];
  for(int i = 0; i < N; i++) cin >> V[i].a >> V[i].b >> V[i].c;
}

bool isValid(int temp, cloth c){
  return c.a <= temp && temp <= c.b;
}

void solve(){
  memset(dp,-1,sizeof(dp));

  for(int i = 0; i < V.size(); i++){
    if(isValid(Temp[0],V[i])) dp[0][i] = 0;
  }

  for(int i = 0; i < D-1; i++){
    for(int j = 0; j < V.size(); j++)
      for(int k = 0; k < V.size(); k++){
	if(dp[i][j] == -1) continue;
	if(!isValid(Temp[i+1],V[k])) continue;
	int diff = abs(V[k].c - V[j].c);
	dp[i+1][k] = max(dp[i+1][k],dp[i][j]+diff);
      }
  }
  int ans = 0;

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

int main(){
  input();
  solve();
  return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int a[1999],b[1999],c[1999],D,N,t[1999],da[1999],da2[1999],dp[2][1999],dp2[2][1999];
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];
    }
    fill(dp[0],dp[0]+1999,-114514);
    fill(dp[1],dp[1]+1999,114514);
    for(int i=0;i<D;i++){
         int kari=0,kari2=114514;

        for(int j=0;j<N;j++){
            if(a[j]<=t[i]&&t[i]<=b[j])dp[0][i]=max(dp[0][i],c[j]);
            if(a[j]<=t[i]&&t[i]<=b[j])dp[1][i]=min(dp[1][i],c[j]);
        }


    }
    int huku=0;

 
    for(int i=1;i<D+1;i++){
        int la=0,lu=0;
        for(int h=0;h<2;h++){
            la=dp[h][i]-dp[0][i-1];
            lu=dp[h][i]-dp[1][i-1];
            if(la<0)la=la*-1;
            if(lu<0)lu=lu*-1;
            int gh=0;
            gh=max(la,lu);
            dp2[h][i]=max(dp2[h][i],gh);
        }
    }
    int kota=0;
    for(int i=0;i<D;i++){
        kota+=max(dp2[0][i],dp2[1][i]);
    }
  

    cout<<kota<<endl;






}

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

int main(){

	int d, n;
	std::cin >> d >> n;

	int data[201][2];
	int dp[201][2];
	int t[201];

	for (int i = 0; i < 201; i++){
		data[i][0] = -1;
		data[i][1] = 10000000;

		dp[i][0] = 0;
		dp[i][1] = 0;
	}

	for (int i = 0; i < d; i++){
		std::cin >> t[i];
	}

	for (int i = 0; i < n; i++){
		int a, b, c;
		std::cin >> a >> b >> c;

		for (int j = 0; j < d; j++){
			if (a <= t[j] && t[j] <= b){
				data[j][0] = std::max(data[j][0], c);
				data[j][1] = std::min(data[j][1], c);
			}
		}
	}

	for (int i = 1; i < d; i++){
		for (int j = 0; j < 2; j++){
			dp[i][j] = std::max(std::abs(data[i - 1][0] - data[i][j]) + dp[i - 1][0], std::abs(data[i - 1][1] - data[i][j]) + dp[i - 1][1]);
		}
	}

	std::cout << std::max(dp[d - 1][0], dp[d - 1][1]) << std::endl;
	return 0;
}