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<iostream>
#include<cstdio>
using namespace std;
int abs(int x){
	if(x<0)return -x;
	return x;
}
int main()
{
	int d,n,t[200],a[100],b[100],c[100];
	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];
	int ans=0;
	int y;
	int x=0;
	for(int i=0;i<d-1;i++){
		if(i==0){
		for(int j=0;j<n;j++){
			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]){
						x=max(x,abs(c[k]-c[j]));
					}
				}
				for(int k=0;k<n;k++){
				if(x==abs(c[k]-c[j]))y=k;
				}
			}
		}
		ans+=x;
		}
		else{
			x=0;
			for(int k=0;k<n;k++){
				if(a[k]<=t[i+1]&&t[i+1]<=b[k]){
					x=max(x,abs(c[k]-c[y]));
				}
			}
			int z=y;
			for(int k=0;k<n;k++){
				if(x==abs(c[k]-c[z]))y=k;
			}
			ans+=x;
		}
	}
	cout << ans << "\n";
	return 0;
}

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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> plli;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define int long long
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>=0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const ll mod = 1e9 + 7;
const ll INF = 1<<30;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const double pi = 3.141592653589793;

int d,n;
int t[205];
vector<pair<int ,pair<int,int>>> cab;
vector<vector<int>> cl(65);
int dp[205][205];

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin  >> d >> n;
    rep(i,d) cin >> t[i];
    rep(i,n){
        int a,b,c;
        cin >> a >> b >> c;
        cab.pb(make_pair(c,make_pair(a,b)));
    }
    rep(i,d)rep(j,n){
        int l=cab[j].se.fi;
        int r=cab[j].se.se;
        if (l<=t[i] && t[i]<=r) cl[t[i]].pb(j);
    }
    rep(i,d+1)rep(j,n) dp[i][j]=-INT_MAX;
    for (auto i: cl[t[0]]){
        for (auto j: cl[t[1]]){
            dp[2][j]=max(dp[2][j],abs(cab[i].fi-cab[j].fi));
        }
    }
    rep2(i,2,d)rep(j,n){
        for (auto k: cl[t[i]]){
            dp[i+1][k]=max(dp[i+1][k],dp[i][j]+abs(cab[j].fi-cab[k].fi));
        }
    }
    int ans=0;
    rep(j,n) ans=max(ans,dp[d][j]);
    cout << ans << endl;
}

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] = max(dp[d+1][j], dp[d][i] + abs(C[i] - C[j]));
				}
			}
		}
	}
	int ans = -INF;
	for(int i=0 ; i < N ; i++ ){
		ans = max(ans, dp[D-1][i]);
	}
	cout << ans << endl;
}

C++: #include<stdio.h>
int as[1001][1001];
int main(void)
{
	int x[1001],s[1001],s1[1001],s2[1001];
	int a,b,A,M=0,G=0,K,i,j,k;
	scanf("%d%d",&a,&b);
	for(i=1;i<=a;i++){
		scanf("%d",&x[i]);
	}
	for(i=0;i<b;i++){
		scanf("%d%d%d",&s[i],&s1[i],&s2[i]);
	}
	A=-100;
	for(i=0;i<=a;i++){
		for(j=0;j<b;j++){
			as[i][j]=A;
		}
	}
	for(i=1;i<=a;i++){
		K=0;
		for(j=0;j<b;j++){
			if(s[j]<=x[i]&&s1[j]>=x[i]){
				as[i][j]=s2[j];
				for(k=0;k<b;k++){
					if(as[i-1][k]!=A){
						G=as[i][j]-as[i-1][k];
						if(G<0){
							G=G*-1;
						}
						if(K<G){
							K=G;
						}
					}
				}
			}
		}
		M+=K;
	//	printf("%d\n",M);
	}
	printf("%d\n",M);
	return 0;
}

C++: #include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, -1, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int D,N;cin>>D>>N;
  int T[D];FOR(i,0,D)cin>>T[i];
  int A[N],B[N],C[N];
  FOR(i,0,N)cin>>A[i]>>B[i]>>C[i];
  ll dp[D][N];
  CLR(dp);
  FOR(i,0,N){
    if(T[0]>=A[i]&&T[0]<=B[i]){
      dp[0][i]=0;
    }
  }
  ll ans=0;
  FOR(i,0,D-1){
    FOR(j,0,N){
      if(dp[i][j]==-1)continue;
      // i+1日目にkをきる
      FOR(k,0,N){
        if(T[i+1]>=A[k]&&T[i+1]<=B[k]){
          dp[i+1][k]=max(dp[i+1][k],dp[i][j]+abs(C[j]-C[k]));
          ans=max(ans,dp[i+1][k]);
        }
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

C++: #include <iostream>
#include <vector>
#include <functional>
#include <queue>
#include <utility>

constexpr int INF = 1000000000;

int n, d;
int dp[210][2]; // 0: max, 1: min
int data[210][2];
int temp[210];

int main() {
    std::cin >> d >> n;

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

    for(int i = 0; i < d; ++i) {
        data[i][0] = -1;
        data[i][1] = INF;
    }

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

        for(int j = 0; j < d; ++j) {
            if(temp[j] >= a && temp[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) {
        dp[i][0] = std::max(
                        dp[i - 1][1] + std::abs(data[i - 1][1] - data[i][0]),
                        dp[i - 1][0] + std::abs(data[i - 1][0] - data[i][0])
                        );
        dp[i][1] = std::max(
                        dp[i - 1][1] + std::abs(data[i - 1][1] - data[i][1]),
                        dp[i - 1][0] + std::abs(data[i - 1][0] - data[i][1])
                        );
    }

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