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<bits/stdc++.h>
using namespace std;
int a,b,c,d,n,memo[500],a1,a2,m1,m2;
vector <pair<int,int> > updown;
vector <int> day;
vector <pair<int,int> > huku;
int solve(int dp,int one,int sum);


int main(){

    cin >> d >> n;
    for(int i=0;i<d;i++){
        cin >> a;
        day.push_back(a);
    }
    for(int i=0;i<n;i++){
        cin >> a >> b >> c;
        updown.push_back(make_pair(a,b));
        huku.push_back(make_pair(c,i));
    }

    std::sort(huku.begin(),huku.end());

    for(int i=0;i<n;i++){
            if(updown[huku[i].second].second>=day[0]&&day[0]>=updown[huku[i].second].first){
                m1=solve(1,huku[i].first,0);
                break;
            }
        }
    for(int i=n-1;i>-1;i--){
            if(updown[huku[i].second].second>=day[0]&&day[0]>=updown[huku[i].second].first){
                m2=solve(1,huku[i].first,0);
                break;
            }
        }


    cout << max(m1,m2) << endl;

return 0;
}


int solve (int dp,int one,int sum){

    if(memo[dp]!=0&&memo[dp]>=sum)return memo[dp];

    int s1=0,s2=0;
    if(dp==d)return sum;
    else {
        for(int i=0;i<n;i++){
            if(updown[huku[i].second].second>=day[dp]&&day[dp]>=updown[huku[i].second].first){
                int sa=max(one,huku[i].first)-min(one,huku[i].first);
                s1=solve(dp+1,huku[i].first,sum+sa);
            }
        }
        for(int i=n-1;i>-1;i--){
            if(updown[huku[i].second].second>=day[dp]&&day[dp]>=updown[huku[i].second].first){
                int sa=max(one,huku[i].first)-min(one,huku[i].first);
                s2=solve(dp+1,huku[i].first,sum+sa);
            }
        }
        return memo[dp]=max(s1,s2);
    }

}

C++: #include<bits/stdc++.h>
using namespace std;
int dp[250][150],T[250],x[250][3],D,N,MAX;
main(){memset(dp,-99999,sizeof(dp));cin>>D>>N;
for(int i=1;i<=D;i++){cin>>T[i];}
for(int i=1;i<=N;i++){cin>>x[i][0]>>x[i][1]>>x[i][2];if(T[1]>=x[i][0] && T[1]<=x[i][1]){dp[1][x[i][2]]=0;}}
for(int i=2;i<=D;i++){for(int j=1;j<=N;j++){if(T[i]>=x[j][0] && T[i]<=x[j][1]){
for(int k=0;k<=100;k++){dp[i][x[j][2]]=max(dp[i][x[j][2]],dp[i-1][k]+abs(x[j][2]-k));}
}}}
for(int i=0;i<=100;i++){MAX=max(MAX,dp[D][i]);}
cout<<MAX<<endl;}

C++: #include<iostream>
#include<algorithm>
#include<memory.h>
using namespace std;
int main()
{
	int n, m, t[1001], c[201],c2[201],v[201],dp[1001][201];
	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> t[i];
	for (int i = 1; i <= m; i++){
		cin >> c[i] >> c2[i] >> v[i];
	}
	memset(dp, -1, sizeof(dp));

	for (int i = 1; i <= m; i++){
		if (t[1] >= c[i] && t[1]<=c2[i])
			dp[1][i] = 0;
	}

	for (int i = 1; i <= n; i++){
		for (int i2 = 1; i2 <= m; i2++){
			if (dp[i][i2] >= 0){
				for (int i3 = 1; i3 <= m; i3++){
					if (t[i + 1] >= c[i3] && t[i + 1] <= c2[i3]){
						dp[i + 1][i3] = max(dp[i][i2] + abs(v[i2] - v[i3]), dp[i+1][i3]);
					}
				}
			}
		}
	}
		int maxv=0;
		for (int i = 1; i <= m; i++){
			maxv = max(maxv, dp[n][i]);
		}
		cout << maxv << endl;
}

C++: #include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
int t[250],a[250],b[250],c[250];
int dp[250][250];
int d,n;
int main()
{
	cin >> d >> n;
	for(int i=1;i<=d;i++)cin >> t[i];
	for(int i=0;i<n;i++)cin >> a[i] >> b[i] >> c[i];
	for(int i=2;i<=d;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(t[i]<a[j]||t[i]>b[j])continue;
			for(int k=0;k<n;k++)
			{
				if(t[i-1]<a[k]||t[i-1]>b[k])continue;
				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][i]);
	}
	cout << ans << endl;
	return 0;
}

C++: #include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;

int D,N;
int T[200];
int A[200];
int B[200];
int C[200];
int dp[200][101];
int main() {
	cin >> D >> N;
	for(int i=0;i<D;i++){
		cin >> T[i];
	}
	memset(dp,-1,sizeof(dp));
	for(int i=0;i<N;i++){
		cin >> A[i] >> B[i] >> C[i];
		if(A[i]<=T[0]&&T[0]<=B[i]){
			dp[0][C[i]]=0;
		}
	}
	for(int i=1;i<D;i++){
		for(int j=0;j<N;j++){
			if(A[j]<=T[i]&&T[i]<=B[j]){
				for(int k=0;k<=100;k++){
					if(dp[i-1][k]!=-1){
						dp[i][C[j]]=max(dp[i][C[j]],dp[i-1][k]+abs(C[j]-k));
						//cout << i << ", " << j << ": " << dp[i][j] << endl;
					}
				}
			}
		}
	}
	int ret=0;
	for(int i=0;i<=100;i++){
		ret=max(ret,dp[D-1][i]);
	}
	cout << ret << 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);
	return 0;
}

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

typedef struct{
	int a; //下限
	int b; //上限
	int c; //派手さ
}clothes;

int d, n;
int t[200];
clothes p[200];

long dp[202][201];

long rec(int x, int y){ //x日目,前の日にきてた服y
	if(dp[x][y]>=0) return dp[x][y];
	
	long ret=0;
	if(x==0){
		for(int i=0; i<n; ++i){
			if(p[i].a<=t[x] && t[x]<=p[i].b){
				int tmp=rec(x+1, i);	
				if(ret<tmp) ret=tmp;
			}
		}	
	}
	else if(x==d) return 0;	
	else{
		for(int i=0; i<n; ++i){
			if(p[i].a<=t[x] && t[x]<=p[i].b){
				int cc=p[i].c-p[y].c;
				if(cc<0) cc=-cc;
				
				int tmp=rec(x+1, i)+cc;	
				if(ret<tmp) ret+=tmp;
			}
		}	
	}
	
	return dp[x][y]=ret;
}

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", &p[i].a, &p[i].b, &p[i].c);
	
	memset(dp, -1, sizeof(dp));
	printf("%ld\n", rec(0,0));	
}