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 <cmath>
using namespace std;
int dayCanW[200];
int dayM[200][200];
int days,clothes;
int clothD[200][3];
int temple[200];

int bestCloth(int Nowday,int yesterday){
  int point=0;
  int pointM=0;
  if(Nowday<days){
    for(int i=0;i<clothes;i++){
      if(temple[Nowday]>=clothD[i][0] && temple[Nowday]<=clothD[i][1]){
	point=bestCloth(Nowday+1,clothD[i][2]);
	if (Nowday!=0){
	  point+=(int)abs((double)clothD[i][2]-yesterday);
	}
	if(point>pointM){
	  pointM=point;
	}
      }
    }
  }
  else{
    return 0;
  } 
  return pointM;//自分の今までの派手さ絶対値の合計（今日ー昨日まで）
}



int main(void){
 
  cin >> days;
  cin >> clothes;
  for(int i=0;i<days;i++){
    cin >> temple[i];
  }
  for(int i=0;i<clothes;i++){
    cin >> clothD[i][0];
    cin >> clothD[i][1];
    cin >> clothD[i][2];
  }
  for(int i=0;i<days;i++){
	dayCanW[i] = 0;
    for(int j=0;j<clothes;j++){
	dayM[i][j] = 0;
    }
  }
  cout << bestCloth(0,0) << endl;
  return 0 ;
}

C++: #include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

const int INF = 1 << 29;
typedef pair<int, int> P;

int d,n;
typedef tuple<int, int, int> C;//温度~温度,派手

int dp[201][201] = {0};

int main(void)
{
	while(cin >> d >> n && n && d)
	{
		memset(dp, 0, sizeof(dp));
		vector<C> cs(n);
		vector<int> atm(d);
		for (int i = 0; i < d; i++)
		{
			cin >> atm[i];
		}
		for (int i = 0; i < n; i++)
		{
			int a, b, c;
			cin >> a >> b >> c;
			cs[i] = make_tuple(a, b, c);
		}

		int ans = 0;
		for (int i = 1; i < d; i++)
		{
			for (int j = 0; j < n; j++)
			{
				int a = get<0>(cs[j]), b = get<1>(cs[j]), c = get<2>(cs[j]);
				if(atm[i] < a || atm[i] > b) continue;
				for (int k = 0; k < n; k++)
				{
					int pa = get<0>(cs[k]), pb=get<1>(cs[k]), pc=get<2>(cs[k]);
					if(atm[i-1] < pa || atm[i-1] > pb) continue;

					 dp[i][j] = max(dp[i][j], abs(c - pc) + dp[i-1][k]);
					 ans = max(dp[i][j],ans);
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

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

#define llong long long 
typedef struct data{
	int low;
	int high;
	int eva;
}data;
int D, N;
int temp[201];
data kind[200];
int score[201][200];

int solve(int d, int k, int yk, int e){
	if(!(d < 2)) e += fabs(kind[yk].eva - kind[k].eva);

	if(e <= score[d][k]) return score[d][k];
	if(d == D) return score[d][k] = e;
	

	int ret = -1;
	for(int i = 0; i < N; i++){
		data use = kind[i];
		if(use.low > temp[d + 1] || use.high < temp[d + 1]) continue;
		ret = max(ret, solve(d + 1, i, k, e));
	}

	return score[d][k] = max(score[d][k], ret);
}

int main(){
	fill_n(temp, 201, -1);
	fill_n(*score, 201 * 200, -1);
	cin >> D >> N;
	for(int i = 1; i <= D; i++){
		cin >> temp[i];
	}
	for(int i = 0; i < N; i++){
		cin >> kind[i].low >> kind[i].high >> kind[i].eva;
	}

	cout << solve(0, 0, 0, 0) << endl;
	return 0;
}

C++: #include<bits/stdc++.h>
#define LL long long
#define FOR(i,a,b) for(int i=a;i<=b;++i)

using namespace std;

static const LL MAX_N = 1e+5;
static const LL INF = 1 << 25;

struct clothes{
    LL A[MAX_N],B[MAX_N],C[MAX_N];
};

int N,D;
LL res=-INF;
LL Day[MAX_N];
LL mem[250][150];
clothes T;

LL cal(LL day,LL p,LL pp,LL sum){
        if(!mem[day][p]){
            res=mem[day][p];
        }
        if(res<sum+abs(pp-p)){
            mem[day][p]=res=sum+abs(pp-p);
            //cout<<"hoge"<<endl;
        }
        if(day==N+1)return 0;
        else{
        if(day==0){
            FOR(i,1,D)
            if(Day[1]>=T.A[i]&&Day[1]<=T.B[i])cal(day+1,T.C[i],p,sum);
        }
        FOR(i,1,D){
            if(Day[day]>=T.A[i]&&Day[day]<=T.B[i]){
                if(day>2)cal(day+1,T.C[i],p,sum+abs(pp-p));
                else cal(day+1,T.C[i],p,sum);
            }
        }
    }
    return mem[day][p]=res;
}


int main(){
    cin>>N>>D;
    FOR(i,1,N)cin>>Day[i];
    FOR(i,1,D){
        cin>>T.A[i]>>T.B[i]>>T.C[i];
    }
    int ans=0;
    cal(0,0,0,0);
    FOR(i,1,150){
        if(ans<mem[N][i])ans=mem[N][i];
    }
    cout<<ans<<endl;
}

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

using namespace std;

#define INF (1 << 30)

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

	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[201], -INF);
	for (int i = 0; i < n; ++i) {
		if (a[i] <= t[0] && t[0] <= b[i]) {
			dp[1][i] = 0;
		}
	}

	for (int i = 1; i < d; ++i) {
		for (int j = 0; j < n; ++j) {
			if (dp[i][j] >= 0) {
				for (int k = 0; k < n; ++k) {
					if (a[k] <= t[i] && t[i] <= b[k]) {
						dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + abs(c[j] - c[k]));
					}
				}
			}
		}
	}

	cout << *max_element(&dp[d][0], &dp[d][n]) << endl;

	return 0;
}

C++: #include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>

using namespace std;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
#define INF 999999
#define rep(i,j) for(int i=0;i<(j);i++)
#define reps(i,j,k) for(int i=j;i<k;i++)
typedef long long ll;
typedef unsigned long long ull;
int d,n;
int hot[512];
int a[512],b[512],c[512];
int dp[512][512];
int main(){
    scanf("%d%d",&d,&n);
    rep(i,d)scanf("%d",&hot[i]);
    rep(i,n)scanf("%d%d%d",&a[i],&b[i],&c[i]);

    memset(dp,-1,sizeof(dp));
    rep(i,n)if(a[i] <= hot[0] &&hot[0] <= b[i])dp[1][c[i]] = 0;

    reps(i,1,d){
        rep(j,256){
            if(dp[i][j] != -1){
                rep(k,n){
                    if(a[k] <= hot[i] && hot[i] <=b[k]){
                        dp[i+1][c[k]] = max(dp[i+1][c[k]],dp[i][j]+abs(c[k]-j));
                    }
                }
            }
        }
    }
    int ans = 0;
    rep(i,256)ans = max(ans,dp[d][i]);
    printf("%d\n",ans);
	return 0;
}