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++: #define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
  
using namespace std;
  
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
  
static const double EPS = 1e-8;
  
static const int tx[] = {0,1,0,-1};
static const int ty[] = {-1,0,1,0};

class Wear{
public:
  int lower_temperature;
  int upper_temperature;
  int gaudiness;
  Wear(int _l,int _u, int _g)
    : lower_temperature(_l),upper_temperature(_u),gaudiness(_g) {}
  Wear() : lower_temperature(0),upper_temperature(0),gaudiness(0){}
};

int main(){
  int total_days;
  int total_wears;
  while(~scanf("%d %d",&total_days,&total_wears)){

    int temperatures[201];
    for(int day=0;day<total_days;day++){
      scanf("%d",temperatures+day);
    }

    Wear wears[201];
    for(int wear_idx=0;wear_idx<total_wears;wear_idx++){
      int lower_temperature,upper_temperature;
      int gaudiness;
      scanf("%d %d %d",&lower_temperature,&upper_temperature,&gaudiness);
      wears[wear_idx] = Wear(lower_temperature,upper_temperature,gaudiness);
    }

    int dp[201][201];
    memset(dp,0,sizeof(dp));

    for(int day = 0; day<total_days; day++){
      for(int from_idx = 0; from_idx < total_wears; from_idx++){
	for(int to_idx = 0; to_idx < total_wears; to_idx++){
	  if(day+1 < total_days
	     && (temperatures[day+1] < wears[to_idx].lower_temperature
		 || wears[to_idx].upper_temperature < temperatures[day+1])) continue;
	  
	  if(temperatures[day] < wears[from_idx].lower_temperature
	     || wears[from_idx].upper_temperature < temperatures[day]) continue;

	  int from = wears[from_idx].gaudiness;
	  int to = wears[to_idx].gaudiness;
	  dp[day+1][to_idx] = max(dp[day+1][to_idx],
				  dp[day][from_idx] + abs(from-to));
	}
      }
    }

    int res = 0;
    for(int wear_idx=0;wear_idx < total_wears;wear_idx++){
      res = max(res,dp[total_days-1][wear_idx]);
    }
    printf("%d\n",res);
  }
}

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

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

int rec(int k, int prev){
	
	if(memo[k][prev] != -1)return memo[k][prev];
	if(k == d)return 0;
	
	int best = 0;
	for(int next = 0; next < n; next++){
		if(t[k] >= a[next] && t[k] <= b[next])
			best = max(best, rec(k + 1, next) + abs(c[next] - c[prev]));
	}
		
	return memo[k][prev] = best;
		
}
int main() {
	for(int i = 0; i <= 200; i++)
		for(int j = 0; j <= 200; j++)
			memo[i][j] = -1;
			
	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;
	for(int i = 0; i < n; i++){
		if(t[0] >= a[i] && t[0] <= b[i])
			ans = max(rec(1, i), ans);
	}

	
	cout << ans << endl;
	
	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 <bits/stdc++.h>
using namespace std;
#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)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int inf = 1e9;
const int mod = 1e9 + 7;

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

    int D, N;
    cin >> D >> N;
    V T(D + 1);
    rep(i, D) cin >> T[i + 1];
    V A(N), B(N), C(N);
    rep(i, N) cin >> A[i] >> B[i] >> C[i];

    VV dp(D + 1, V(101, -inf));
    dp[0][0] = 0;
    rep(i, D) {
        rep(c, 101) {
            rep(j, N) {
                if (A[j] <= T[i + 1] && T[i + 1] <= B[j]) {
                    dp[i + 1][C[j]] = max(dp[i + 1][C[j]], dp[i][c] + (i != 0) * abs(C[j] - c));
                }
            }
        }
    }

    cout << *max_element(all(dp[D])) << endl;
}

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

struct Cloth
{
	int mini, maxi, glitz;
	bool operator<(const Cloth& c) const
	{
		if (this->glitz < c.glitz) return true;
		else if (this->glitz == c.glitz){
			if (this->mini < c.mini) return true;
			else if (this->mini == c.mini && this->maxi < c.maxi) return true;
			return false;
		}
		return false;
	}
};

int d, n;
int temp[256];
Cloth cloth[256];
int memo[256][256];

int solve(int day, int before);

int main()
{
	scanf("%d %d", &d, &n);
	for (int i = 1; i <= d; i++) scanf("%d", temp + i);
	for (int i = 1; i <= n; i++){
		scanf("%d %d %d", &cloth[i].mini, &cloth[i].maxi, &cloth[i].glitz);
	}
	cloth[0] = cloth[1];
	//sort(cloth, cloth + n);
	memset(memo, -1, sizeof(memo));
	
	solve(1, 0);
	int maxi = 0;
	for (int i = 1; i <= d; i++){
		for (int j = 1; j <= n; j++){
			maxi = max(maxi, memo[i][j]);
		}
	}
	printf("%d\n", maxi);
	/*
	for (int i = 1; i <= d; i++){
		for (int j = 1; j <= n; j++){
			printf("%d ", memo[i][j]);
		}
		puts("");
	}*/
	
	return 0;
}

int solve(int day, int before)
{
	if (day > d) return 0;
	if (memo[day][before] >= 0) return memo[day][before];
	
	int t = 0;
	for (int i = 1; i <= n; i++){
		if (cloth[i].mini <= temp[day] && temp[day] <= cloth[i].maxi){
			/*
			printf("%*d %d\n", day, day, i);
			printf("%*s %d %d %d %d\n", day, "", solve(day + 1, i), cloth[before].glitz, cloth[i].glitz, t);
			*/
			t = max(t, solve(day + 1, i) + abs(cloth[before].glitz - cloth[i].glitz));
			/*
			printf("%*d %d\n", day, day, i);
			printf("%*s %d %d %d %d\n", day, "", solve(day + 1, i), cloth[before].glitz, cloth[i].glitz, t);
			*/
		}
	}
	
	return memo[day][before] = t;
}