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++: #include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
//dp[i][j]: i??\???j???????????????c_x_(i)-c_x_(i-1)????????§???
int dp[201][201];
int main(){
    int d,n,ans=0;
    cin>>d>>n;
    int a[201],b[201],c[201],tem[201];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<d;i++)
        cin>>tem[i];
    for(int i=0;i<n;i++)
        cin>>a[i]>>b[i]>>c[i];
    for(int m=1;m<d;m++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                if(a[i]<=tem[m]&&tem[m]<=b[i]  &&  a[j]<=tem[m-1]&&tem[m-1]<=b[j])
                    dp[m][i]=max(dp[m][i],abs(c[i]-c[j])+dp[m-1][j]);
    for(int i=0;i<n;i++)
        ans=max(ans,dp[d-1][i]);
    cout<<ans<<endl;
}

C++: #include<iostream>

int weather[201],cloth[201][3],dp[201][201];

bool can[201][201];

int main(){
	int day,wear;
	std::cin>>day>>wear;
	for(int i=1;i<=day;i++){
		std::cin>>weather[i];
	}
	for(int i=1;i<=wear;i++){
		std::cin>>cloth[i][0]>>cloth[i][1]>>cloth[i][2];
	}
	for(int i=1;i<=day;i++){
		for(int j=1;j<=wear;j++){
			if(cloth[j][0]<=weather[i]&&weather[i]<=cloth[j][1])can[i][j]=true;
		}
	}
	for(int i=2;i<=day;i++){
		for(int j=1;j<=wear;j++){
			for(int k=1;k<=wear;k++){
				if(can[i][j]&&can[i-1][k]){
					dp[i][j]=std::max(dp[i][j],dp[i-1][k]+std::abs(cloth[k][2]-cloth[j][2]));
				}
			}
		}
	}
	int max=0;
	for(int i=1;i<=wear;i++){
		max=std::max(dp[day][i],max);
	}
	std::cout<<max<<std::endl;
	return 0;
}

C++: #include<cstdio>
#define MAX_N 200

int max (int a,int b){
	if(a>b) return a;
	else return b;
}

int min (int a,int b){
	if(a<b) return a;
	else return b;
}

int abs(int i){
	if(i<0) return i*-1;
	else return i;
}

//maxxxxxxxxxxxzzzzzz dpppppp!!!!!!!!

int D,N;
int dp[MAX_N+1][MAX_N+1];
int T[200];
int C[200][3];



int main(){
	scanf("%d%d",&D,&N);
	for(int i=0;i<=D;i++){
		for(int ii=0;ii<=N;ii++){
			dp[i][ii]=-1;
		}
	}
	for(int i=0;i<D;i++)
		scanf("%d",&T[i]);
	for(int i=0;i<N;i++)
		scanf("%d%d%d",&C[i][0],&C[i][1],&C[i][2]);
	for (int j = 0; j < N; j++) if (C[j][0] <= T[0] && T[0] <= C[j][1]) 
		dp[0][j] = 0;
	
	for(int d=0;d<D-1;d++){
		for(int c=0;c<N;c++){
			if(dp[d][c]>=0){
				for(int i=0;i<N;i++){
					if (C[i][0] <= T[d+1] && T[d+1] <= C[i][1]) 
						dp[d+1][i]=max(dp[d+1][i],dp[d][c]+abs(C[c][2]-C[i][2]));
				}
			}
		}
	}

	int ans = -1;
	for (int j = 0; j < N; j++) {
		if (ans < dp[D-1][j]) {
			ans = dp[D-1][j];
		}
	}
	printf("%d\n", ans);
	return 0;
}

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

int main(){
	int D,N;
	int Kion[200];
	int Fmin[200],Fmax[200],Fhad[200];
	cin>>D>>N;
	for(int i=0;i<D;i++){
		cin>>Kion[i];
	}
	for(int i=0;i<N;i++){
		cin>>Fmin[i]>>Fmax[i]>>Fhad[i];
	}

	int Kekka[200][200];
	int rinji,rin2;
	//1??\???
	for(int i=0;i<N;i++){
		if(Kion[0]>=Fmin[i]&&Kion[0]<=Fmax[i]) Kekka[0][i]=0;
		else Kekka[0][i]=-1;
	}
	//2??\?????\???
	for(int day=1;day<D;day++){
		rinji=-1,rin2=0;
		for(int fuku=0;fuku<N;fuku++){
			if(Kion[day]>=Fmin[fuku]&&Kion[day]<=Fmax[fuku]){
				for(int mf=0;mf<N;mf++){
					if(Kekka[day-1][mf]!=-1&&rinji<abs(Fhad[mf]-Fhad[fuku])) {rinji=abs(Fhad[mf]-Fhad[fuku]);rin2=mf;}
				}
				Kekka[day][fuku]=Kekka[day-1][rin2]+rinji;
			}
			else{
				Kekka[day][fuku]=-1;
			}
		}
	}
	rinji=0;
	for(int i=0;i<N;i++){
		rinji=max(rinji,Kekka[D-1][i]);
	}
	cout<<rinji<<endl;
	return 0;
}

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

int main(){
	int a,b;
	cin>>a>>b;
	vector<int> d(a),mn(b),mx(b),ha(b);
	for(int i=0; i<a; i++) cin>>d[i];
	for(int i=0; i<b; i++) cin>>mn[i]>>mx[i]>>ha[i];
	vector<vector<int>> dp(a,vector<int>(b,0));
	for(int i=0; i<b; i++){
		if(mn[i] > d[0] || d[0] > mx[i]){
			dp[0][i] = -INT_MAX;
		}
	}
	for(int i=1; i<a; i++){
		for(int j=0; j<b; j++){
			if(mn[j] <= d[i] && d[i] <= mx[j]){
				for(int k=0; k<b; k++){
					dp[i][j] = max(dp[i][j], dp[i-1][k] + abs(ha[j] - ha[k]));
				}
			}else{
				dp[i][j] = -INT_MAX;
			}
		}
	}
	int ans = -INT_MAX;
	for(int x : dp[a-1]){
		ans = max(ans,x);
	}
	cout<<ans<<endl;
}

C++: #include "stdio.h"

int day;
int num;
int temp[201];
int wear[200];
int dp[200][200] = {};
int min[201] = {};
int max[201] = {};
int ans=0;

int abs(int a) {
	if (a > 0)return a;
	return -a;
}

int Max(int a, int b) {
	if (a > b)return a;
	return b;
}

int main() {
	scanf("%d %d", &day, &num);
	for (int i = 0; i < day; i++) {
		scanf("%d", &temp[i + 1]);
	}
	for (int i = 0; i < num; i++) {
		scanf("%d %d %d", &min[i], &max[i], &wear[i]);
	}
	for (int i = 2; i <= day; i++) {
		for (int j = 0; j < num; j++) {
			if (temp[i] >= min[j] && temp[i] <= max[j]) {
				for (int k = 0; k < num; k++) {
					if (temp[i-1] >= min[k] && temp[i-1] <= max[k]) {
						dp[i][j] = Max(dp[i][j], dp[i - 1][k] + abs(wear[k] - wear[j]));
					}
				}
			}
		}
	}
	for (int i = 0; i < num; i++)ans = Max(ans, dp[day][i]);
	printf("%d\n", ans);
	return 0;

}

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

int D,N,T[210],A[210],B[210],C[210];
int dp[210][210] = {{0}};
int main(){
	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];
		dp[0][i] = 0;
	}
	for(int i=1;i<=D;i++){
		for(int j=1;j<=N;j++){
			if(A[j]<=T[i] && T[i]<=B[j]){
				if(i==1) dp[i][j] = 0;
				else{
					for(int k=1;k<=N;k++){
						if(dp[i-1][k]!=-1){
							dp[i][j] = max(dp[i][j],dp[i-1][k]+abs(C[j]-C[k]));
						}
					}
				}
			}else dp[i][j] = -1;
		}
	}
	int ans = 0;
	for(int i=1;i<=N;i++){
		ans = max(ans,dp[D][i]);
	}
	cout << ans << endl;
}

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