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 <string.h>
#include <cmath>
using namespace std;

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

int rec(int d, int c){
	if(d == D)
		return 0;
	if(memo[d][c] != -1)
		return memo[d][c];
	
	int res = 0;	
	for(int i = 0; i < N; ++i){
		if(A[i] <= T[d] && T[d] <= B[i])
			res = max(res, rec(d + 1, C[i]) + abs(c - C[i]));
	}
	return memo[d][c] = res;
}

int main() {
	memset(memo, -1, sizeof(memo));
	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(A[i] <= T[0] && T[0] <= B[i])
			ans = max(ans, rec(1, C[i]));
	}
	cout << ans << endl;
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int a[500],b[500],c[500],D,N,t[500],dp[500][500];
int main(){
    cin>>D>>N;
    for(int i=1;i<D+1;i++){ cin>>t[i]; }
    for(int i=1;i<N+1;i++){ cin>>a[i]>>b[i]>>c[i]; }
    for(int i=1;i<D+1;i++){ fill(dp[i]+1,dp[i]+N+1,-1); }
    for(int i=1;i<N+1;i++){ if(a[i]<=t[1]&&t[1]<=b[i]){ dp[1][i]=0; } }
    for(int i=2;i<D+1;i++){
        for(int j=1;j<N+1;j++){
            if(dp[i-1][j]!=-1){
                for(int u=1;u<N+1;u++){
                    if(a[u]<=t[i]&&t[i]<=b[u]){
                        int cu=c[j]-c[u];
                        if(cu<0)cu=cu*-1;
                        dp[i][u]=max(dp[i][u],dp[i-1][j]+cu);
                    }
                }
            }
        }
    }
    int kotae=0;
    for(int i=1;i<N+1;i++){ kotae=max(kotae,dp[D][i]); }
    cout<<kotae<<endl;
}

C++: #include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1e8;
int main(){
	int n,m;
	cin>>n>>m;
	vi te(n);
	rep(i,n)cin>>te[i];
	vvi in(m,vi(3));
	rep(i,m)rep(j,3)cin>>in[i][j];
	vvi dp(n,vi(m));
	loop(i,1,n)rep(j,m)if(in[j][0]<=te[i]&&te[i]<=in[j][1]){
		int mi=0;
		rep(k,m)if(in[k][0]<=te[i-1]&&te[i-1]<=in[k][1])
			mi=max(mi,dp[i-1][k]+abs(in[j][2]-in[k][2]));
		dp[i][j]=max(dp[i][j],mi);
	}
	int out=0;
	rep(i,m)out=max(out,dp[n-1][i]);
	cout<<out<<endl;
}

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

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

struct Dress{
  int A, B, C;
};

const int MAX = 210;

bool canWear(int temp, Dress d){
  return (d.A <= temp && temp <= d.B);
}

int main(){
  int D, N;
  cin >> D >> N;
    vector<Dress> dress(D);    
    vector<int> temp(N);
    rep(i, D) cin >> temp[i];
    rep(i, N) cin >> dress[i].A >> dress[i].B >> dress[i].C;
    
    int dp[MAX][MAX];
    memset(dp, -1, sizeof(dp));
    rep(i, N) if(canWear(temp[0], dress[i])) dp[0][i] = 0;
    
    REP(i, 1, D){
      REP(j, 0, N){
	REP(k, 0, N){
	  if(dp[i-1][j] == -1) continue;
	  
	  if(canWear(temp[i], dress[k])) dp[i][k] = max(dp[i][k], dp[i-1][j] + abs(dress[j].C - dress[k].C));
	}
      }
    }
    
    int ans = -1;
    rep(i, N) ans = max(ans, dp[D-1][i]);
    cout << ans << endl;
    return 0;
}

C++: #include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define vi vector<int>
#define pb push_back
#define INF 999999999
//#define INF (1LL<<59)

struct st{
	int lower,upper,c;
};

int main(){
	int d,n;
	cin>>d>>n;
	vector<int> day(d);
	vector<st> clo(n);
	rep(i,d)cin>>day[i];
	rep(i,n)cin>>clo[i].lower>>clo[i].upper>>clo[i].c;
	
	int dp[300][200];
	rep(i,300)rep(j,200)dp[i][j] = -INF;
	
	rep(i,d){
		int t = day[i];
		for(int j=0;j<n;j++){
			if( clo[j].lower<=t && t<=clo[j].upper ){
				if(i==0)dp[0][clo[j].c] = 0;
				else{
					rep(k,200){
						dp[i][clo[j].c] = max( dp[i-1][k]+(int)abs(k-clo[j].c) , dp[i][clo[j].c] );
					}
				}
			}
		}
	}
	
	
	int ans = 0;
	rep(i,200){
		ans = max(ans,dp[d-1][i]);
	}
	cout<<ans<<endl;
}

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

int main(){
    int d, n, t[201], a[201], b[201], c[201], dp[201][201] = {}, ans = 0;
    bool can[201][201];

    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];
    }

    for(int i = 1; i <= d; i++){
        for(int j = 1; j <= n; j++){
            if(a[j] <= t[i] && t[i] <= b[j]){
                can[i][j] = 1;
            }
        }
    }


    for(int i = 1; i <= d; i++){
        for(int j = 1; j <= n; j++){
            if(can[i][j]){
                for(int l = 1; l <= n; l++){
                    if(can[i - 1][l]){
                        int x = ((c[j] > c[l])? c[j] - c[l]: c[l] - c[j]);
                        dp[i][j] = max(dp[i][j], x + dp[i - 1][l]);
                    }
                }
            }
            if(i == d){
                ans = max(ans, dp[i][j]);
            }
        }
    }

    cout << ans << endl;

    return 0;
}

C++: #include<iostream>
#include<vector>
#include<cmath>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int main(){
	int d,n,alt,cnt=0,ans=0;
	cin>>d>>n;
	int t[d],a[n],b[n],c[n];
	rep(i,d)cin>>t[i];
	rep(i,n)cin>>a[i]>>b[i]>>c[i];
	vector<int> can[d];
	rep(i,d){
		rep(j,n){
			if(a[j]<=t[i] && b[j]>=t[i])can[i].push_back(c[j]);
		}
	}
	int calc[2][d];
	rep(i,d){
		if(i%2==0)alt=10000;
		else alt=-1;
		rep(j,can[i].size()){
			if(i%2==0){
				alt=min(alt,can[i][j]);
			}else{
				alt=max(alt,can[i][j]);
			}
		}
		calc[0][i]=alt;
	}
	rep(i,d){
		if(i%2==0)alt=-1;
		else alt=10000;
		rep(j,can[i].size()){
			if(i%2==0){
				alt=max(alt,can[i][j]);
			}else{
				alt=min(alt,can[i][j]);
			}
		}
		calc[1][i]=alt;
	}
	rep(i,d-1){
		ans+=abs(calc[0][i]-calc[0][i+1]);
		cnt+=abs(calc[1][i]-calc[1][i+1]);
	}
	ans=max(ans,cnt);
	cout<<ans<<endl;
	return 0;
}