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++: //
//  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>
using namespace std;
#define Rep(i,N) for(int i = 0; i < N; i++)
#define INF 1 << 28
#define S second
#define F first
typedef pair<int,int> Pi;

inline void chmax(int &a, int b) { a = max(a,b); }
inline void chmin(int &a, int b) { a = min(a,b); }

int main()
{
  int D, N;
  int data[205];
  int A[205], B[205], C[205];
  
  cin >> D >> N;
  Rep(i,D) cin >> data[i];
  Rep(i,N) cin >> A[i] >> B[i] >> C[i];

  int dp[205][205];
  Rep(i,N) {
    if(data[0] >= A[i] && data[0] <= B[i])dp[0][i] = 0;
    else dp[0][i] = -INF;
  }
  fill(dp[1],dp[205],-INF);
  for(int i = 1; i < D; i++) {
    Rep(j,N) {
      if(data[i] < A[j] || data[i] > B[j]) continue;
      Rep(k,N) {
	if(dp[i - 1][k] == -INF)continue;
	chmax(dp[i][j], dp[i - 1][k] + abs(C[j] - C[k]));
      }
    }
  }
  cout << *max_element(dp[D - 1],dp[D - 1] + N) << endl;
  return 0;
}

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

using namespace std;

typedef struct {
	int a, b, c;
} fuku_t;

int d, n;

int t[200];
fuku_t fuku[200];

int dp[200][200];

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", &fuku[i].a, &fuku[i].b, &fuku[i].c);

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

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

	int ans = 0;

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

	printf("%d\n", ans);
}

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 e){
	//cout << d << " " << k << " " << e << "   " << score[d][k] << endl;
	score[d][k] = max(score[d][k], e);
	if(score[d][k] > e) return 0;
	if(d == D) return e;


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

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

int main(){
	fill_n(temp, 201, -1);
	fill_n(*score, 201 * 200, 0);
	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, -1) << endl;
	return 0;
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
int dp[110][110],l[110],r[110],p[110],n,m,a[110];
int main(){
	cin>>n>>m;for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<m;i++)cin>>l[i]>>r[i]>>p[i];
	for(int i=0;i<12100;i++)dp[i/110][i%110]=-1000000000;
	for(int i=0;i<m;i++){
		if(l[i]<=a[0] && a[i]<=r[0]){
			dp[0][p[i]]=max(dp[0][p[i]],0);
		}
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<=100;j++){
			for(int k=0;k<m;k++){
				if(l[k]<=a[i] && a[i]<=r[k]){
					dp[i][p[k]]=max(dp[i][p[k]],dp[i-1][j]+abs(j-p[k]));)
				}
			}
		}
	}
	int maxn=0;for(int i=0;i<=100;i++)maxn=max(maxn,dp[n-1][i]);
	cout<<maxn<<endl;
	return 0;
}

C++: #include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
typedef long long ll;
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)

int main(void){
	int d, n;//??\??°??????????¨????
	cin >> d >> n;
	vector<int> t(d);
	rep(i, d) cin >> t[i];
	vector<int> a(n), b(n), c(n);//??????????????§????´???????
	rep(i, n) cin >> a[i] >> b[i] >> c[i];

	int dp[201][201];//dp[i][j] i(1~d)??\??????j(0~n)????????????????????????????????§???
	rep(j, d) dp[0][j] = 0;//?????????
	reps(i, 1, d){//??\
		rep(j, n){//????????????
			rep(k, n){//?????????????????¨??¢?´¢??§??¢????????????
				if(a[k] <= t[i] && t[i] <= b[k]){
					dp[i][k] = max(dp[i][k], dp[i - 1][j] + abs(c[k] - c[j]));
					//printf("i %d j %d k %d dp%d\n", i, j, k, dp[i][k]);
				} 
			}
		}
	}


	int ans = 0;
	rep(i, n){
		ans = max(ans, dp[d - 1][i]);
	}
	printf("%d\n", ans);
	return 0;
}