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++: // AOJ 0579
#include<iostream>
using namespace std;

const int DMAX = 300, NMAX = 300;
const int INF = 1e4;
int d, n;
int T[DMAX], A[NMAX], B[NMAX], C[NMAX];
int black[NMAX], red[NMAX];
int dp[2][DMAX];

int diff(int x, int y) {
  return (x > y ? x - y:y - x);
}

int solve() {
  for (int day = 0; day < d; day++) {
    black[day] = INF, red[day] = -1;
  }

  for (int day = 0; day < d; day++) {
    for (int cloth = 0; cloth < n; cloth++) {
      if (A[cloth] <= T[day] and T[day] <= B[cloth]) {
        black[day] = min(black[day], C[cloth]);
        red[day] = max(red[day], C[cloth]);
      }
    }
  }

  for (int day = 1; day < d; day++) {
    dp[0][day] =  
      max(dp[0][day-1] + diff(red[day],red[day-1]), 
          dp[1][day-1] + diff(red[day],black[day-1]));
    dp[1][day] =  
      max(dp[0][day-1] + diff(black[day],red[day-1]), 
          dp[1][day-1] + diff(black[day],black[day-1]));
//    cout << dp[0][day] << " " << dp[1][day] << endl;
  }

  return max(dp[0][d-1], dp[1][d-1]);
}

int main() {
  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];
  }

  cout << solve() << endl;
}

C++: #include <iostream>
#include <cstring>
#include <cstdlib>

using namespace std;

int dp[201][101],tep[201],a[201],b[201],c[201];
int main(){
    int d,n;
    cin>>d>>n;
    for(int i=0;i<d;++i) cin>>tep[i];
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<n;++i){
        cin>>a[i]>>b[i]>>c[i];
        if(a[i]<=tep[0]&&b[i]>=tep[0]) dp[0][c[i]]=0;
    }
    for(int i=0;i<d-1;++i){
        for(int j=0;j<101;++j){
            if(dp[i][j]==-1) continue;
            for(int k=0;k<n;++k){
                if(a[k]<=tep[i+1]&&b[k]>=tep[i+1]){
                    dp[i+1][c[k]]=max(dp[i+1][c[k]],dp[i][j]+abs(j-c[k]));
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<101;++i) ans=max(ans,dp[d-1][i]);
    cout<<ans<<endl;
    return 0;
}

C++: //
//  main.cpp

#include <iostream>
#include <cmath>


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 "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

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

int dp(int d, int b)
{
	if (memo[d][b] != -1) { return memo[d][b]; }
	if (d == 0) { return memo[d][b] = 0; }
	int res = 0;
	rep(i, N)
	{
		if (A[i] <= T[d - 1] && T[d - 1] <= B[i])
		{
			memo[d - 1][C[i]] = dp(d - 1, C[i]) + abs(b - C[i]);
			if (d == D) { memo[d - 1][C[i]] -= abs(b - C[i]); }
			res = std::max(res, memo[d - 1][C[i]]);
		}
	}
	return memo[d][b] = res;
}

int main()
{
	memset(memo, -1, sizeof(memo));
	in >> D >> N;
	rep(i, D) { in >> T[i]; }
	rep(i, N) { in >> A[i] >> B[i] >> C[i]; }
	out << dp(D, 0) << std::endl;
	return 0;
}

C++: #include <iostream>		//cin, cout
#include <algorithm>	//max()
#include <cmath>		//abs()
using namespace std;

int d, n;
int t[200];
int a[200], b[200], c[200];
int dp[201][200];			//dp[day][fuku] = sum????????§???
int ans = -1145141919;		//??????

//dp????????????????????¨?????????????????´??°??§????????°???ans????±?????????????
void makeAns(){
	int day, fuku, i;
	
	//?????????
	for( day = 0; day < d + 1; day++ ){
		for( fuku = 0; fuku < n; fuku++ )
			dp[day][fuku] = -114514;
	}
	for( fuku = 0; fuku < n; fuku++ ){
		if( a[fuku] <= t[0] && t[0] <= b[fuku] )
			dp[1][fuku] = 0;	//0??\?????????fuku???????????´???
	}
	
	//dp???????????´??°
	for( day = 1; day < d; day++ ){
		for( fuku = 0; fuku < n; fuku++ ){
			//day??\?????????????±???????(????§?)
			for( i = 0; i < n; i++ ){
				if( a[i] <= t[day] && t[day] <= b[i] ){
					//day??\?????????i?????????
					dp[day + 1][i] = max(dp[day + 1][i], dp[day][fuku] + abs(c[fuku] - c[i]));
				}
			}
		}
	}
	
	//??????????¨??????????
	for( i = 0; i < n; i++ ){
		ans = max(ans, dp[d][i]);
	}
}

int main()
{
	int i, j;
	cin >> d >> n;
	for( i = 0; i < d; i++ ) cin >> t[i];
	for( i = 0; i < n; i++ ) cin >> a[i] >> b[i] >> c[i];
	makeAns();
	cout << ans << endl;
	return 0;
}