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 := 1; 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++: //Hot Days
#include <iostream>

using namespace std;

static const int NIL = -1;

struct Clothes {
    int a, b, c;
    Clothes() {}
    Clothes(int a, int b, int c): a(a), b(b), c(c) {}
};

int main() {
    int D, N, a, b, c;
    cin >> D >> N;
    int T[D];
    Clothes C[N];
    for(int i = 0; i < D; i++) cin >> T[i];
    for(int i = 0; i < N; i++) {
        cin >> a >> b >> c;
        C[i] = Clothes(a, b, c);
    }

    int dp[D][101];

    for(int i = 0; i < D; i++) for(int j = 0; j < 101; j++) dp[i][j] = NIL;
    for(int i = 0; i < D; i++) {
        for(int j = 0; j < N; j++) {
            if(C[j].a <= T[i] && C[j].b >= T[i]) {
                if(i == 0) dp[0][C[j].c] = 0;
                else {
                    for(int k = 0; k < 101; k++) {
                        if(dp[i - 1][k] == NIL) continue;
                        dp[i][C[j].c] = max(dp[i][C[j].c], dp[i - 1][k] + abs(k - C[j].c));
                    }
                }
            }
        }
    }

    int maxv = 0;
    for(int i = 0; i < 101; i++) {
        maxv = max(maxv, dp[D - 1][i]);
    }
    cout << maxv << endl;
}

C++: //
//  main.cpp

#include <iostream>

using namespace std;
struct status{
	int toptemp;
	int bottomtemp;
	int fancy;
	
};
status dress[201];
int dp[201][201];//i??\???????????????j????????????????????§????´???????
int temp[201];
int D,N;

int MAX(int i,int j){//i??\?????????j???????????????????????§???????????????
	if(i == 0){//?????\????????????????????????
//		return dress[j].fancy;
		return 0;
	}
	
//	for(int i=0;i<N;i++){
	for(int J=0;J<N;J++){//i-1??\?????????J(1<D)???????????????????????§???
		if(temp[i-1] >= dress[J].bottomtemp && temp[i-1] <= dress[J].toptemp){
			dp[i][j] = max(dp[i][j],MAX(i-1,J) + abs(dress[J].fancy - dress[j].fancy));
		}
	}
	return dp[i][j];
//		dp[i-1][j]
//	}
}

int main(){	
	
	cin >> D >> N;
	
	
	for(int i=0;i<D;i++){
		cin >> temp[i];
	}
	for(int i=0;i<N;i++){
		cin >> dress[i].bottomtemp >> dress[i].toptemp >> dress[i].fancy;
	}
	

	for(int i=0;i<201;i++){
		for(int j=0;j<201;j++){
			dp[i][j] = -1;
		}
	}
	int answer=0;
	for(int i=0;i<N;i++){
		if(temp[D-1] >= dress[i].bottomtemp && temp[D-1] <= dress[i].toptemp){
			answer = max(answer,MAX(D-1,i));
		}
	}
	cout << answer << endl;
	
	/*
	for(int i=0;i<N;i++){//0??\?????????????¨???????
		if(temp[0] >= dress[i].bottomtemp && temp[0] <= dress[i].toptemp){
			dp[0][i] = dress[i].fancy;
		}
	}
	
	for(int i=1;i<D;i++){
		for(int j=0;j<N;j++){
			if(temp[i] >= dress[j].bottomtemp && temp[i] <= dress[j].toptemp){//i??\??????j??????????????????
				int Maxfancy=-1;
				for(int k=0;k<N;k++){//i-1??\????????¨????????????????????´???????????????????´???????????????§???????????????????????????
					if(dp[i-1][k] == -1)continue;
					Maxfancy = max(Maxfancy,abs(dress[j].fancy - dress[k].fancy));
				}
				dp[i][j] = Maxfancy;
			}
		}
	}
	
	int answer = 0;
	for(int i=1;i<D;i++){
		int Max = -1;
		for(int j=0;j<N;j++){
			Max = max(Max,dp[i][j]);
		}
		answer += Max;
	}
	cout << answer << endl;
	
	vector<int> dresses;
	int matrix[201][2];
	for(int i=0;i<D;i++){
		for(int j=0;j<N;j++){
			if(temp[i] >= dress[j].bottomtemp && temp[i] <= dress[j].toptemp){
				dresses.push_back(dress[j].fancy);
			}
		}
		sort(dresses.begin(),dresses.end());
		matrix[i][0] = dresses[0];
		matrix[i][1] = dresses[dresses.size() - 1];
	}
	
	int dp[201]={};
	dp[0] = max(matrix[0][0],matrix[0][1]);
	
	for(int i=1;i<D;i++){
		dp[i] = max(abs(dp[i-1] - matrix[i][0]),abs(dp[i-1] - matrix[i][1]));
	}
	
	cout << dp[D-1] << endl;
	*/
	return 0;
}

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

 int master(int data){
 if(data>=0)
	 return data;
 return -data;
 }
int main(){
    int D,N,T[200],A[200][3];
    int dp[200][101];
    cin >> N >> D ;
    for(int i=0;i<N;i++){
        cin >>T[i];
    }
    for(int i=0;i<D;i++){
        for(int j=0;j<3;j++){
            cin >>A[i][j];
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<100;j++){
            dp[i][j]=-9999;
        }
    }
    for(int l=0;l<D;l++){
        if(T[0]>A[l][0] && T[0]<A[l][1] ){
            dp[ 0 ][ A[l][2] ]=0;
             
 
        }
    }
    for(int i=1;i<N;i++){
        for(int j=0;j<D;j++){
            if(T[i]>=A[j][0] && T[i]<=A[j][1] ){
                for(int l=0;l<=100;l++){
                    if(dp[i-1 ][ l ]>=0)
                        dp[ i ][ A[j][2] ]=max(dp[ i ][ A[j][2] ],dp[ i-1 ][ l ]+master(l-A[j][2]));//テッツセツεッツスツ、テッツセツづッツスツサテッツセツづァツ板佚ッツスツ」テッツセツ?テッツスツセテッツセツεッツスツ」テッツセツ?テッツスツァテッツセツεッツスツ」テッツセツ?テッツスツョテッツセツεッツスツヲテッツセツづヲツ??テッツスツゥテッツセツづッツスツォテッツセツづ、ツスツ堙ッツスツ」テッツセツ??テッツスツ、テッツセツづッツスツサテッツセツづァツ板佚ッツスツ・テッツセツづ・ツエツ「?
                     
 
                }
            }
        }
    }
    int answer=0;
    for(int j=0;j<101;j++)
    {
		
        answer=max(answer,dp[ N-1 ][j]);
    }
    cout << answer << endl;
    return 0;
}

C++: #include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define INF (1<<28)
#define MD 200
#define MN 100
int D, N;
int T[MD+1];
int CA[MN+1], CB[MN+1], CC[MN+1];

int memo[MD+1][MN+1];
int solve(int day, int cloth) {
    if (day > D) return 0;
    if (not (CA[cloth] <= T[day] && T[day] <= CB[cloth])) return -INF;
    if (memo[day][cloth] >= 0) return memo[day][cloth];
    int ret = 0;
    for (int i = 0; i < N; i++) {
        ret = max(ret, abs(CC[i] - CC[cloth]) + solve(day+1, i));
    }
    return memo[day][cloth] = 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", CA+i, CB+i, CC+i);
    memset(memo, -1, sizeof(memo));
    int ans = 0;
    for (int i = 0; i < N; i++) {
        ans = max(ans, solve(0, i));
    }
    printf("%d\n", ans);
    return 0;
}

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

using i64 = int64_t;

struct Cloth{
    int a, b, c;
};

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

int main(){
    int d, n;
    cin >> d >> n;
    vector<int> t;
    t.push_back(0);
    for(int i=0;i<d;++i){
        int tmp;
        cin >> tmp;
        t.push_back(tmp);
    }
    vector<Cloth> c;
    c.push_back((Cloth){0, 0, 0});
    for(int i=0;i<n;++i){
        int x, y, z;
        cin >> x >> y >> z;
        c.push_back((Cloth){x, y, z});
    }

    for(int i=1;i<=n;++i){
        if(t[1] < c[i].a || t[1] > c[i].b){
            dp[1][i] = -1;
        }
    }

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

    int ans = 0;
    for(int i=1;i<=n;++i)ans = max(ans, dp[d][i]);
    cout << ans << endl;

    return 0;
}