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<stdio.h>
#include<math.h>
#include<algorithm>
#include<cctype>
#include<string.h>
#include <stdlib.h>

#define PI 3.1415926
void swap(int* x, int* y) {
	int a = *x;
	int b = *y;
	*x = b;
	*y = a;
}
int factorial(int n);
int sum(int n, int*);
int ave(int n, int*);
int min(int n, int*), min(int n, int m);
int max(int n, int*), max(int n, int m);

int main() {
	int D, N, T[400], A[400], B[400], C[400], X[20][400] = { 0 };
	int F[10][400] = { 0 };
	int f[10][400];
	int ans = 0;
	scanf("%d %d", &D, &N);
	for (int i = 1; i <= D; i++) {
		scanf("%d", &T[i]);
	}
	for (int i = 1; i <= N; i++) {
		scanf("%d %d %d", &A[i], &B[i], &C[i]);
	}
	for (int i = 1; i <= D; i++) {
		X[1][i] = 100;
	}
	for (int i = 1; i <= D; i++) {
		for (int j = 1; j <= N; j++) {
			if (A[j] <= T[i] && B[j] >= T[i] && C[j] > X[0][i]) {
				X[0][i] = C[j];
			}
			if (A[j] <= T[i] && B[j] >= T[i] && C[j] < X[1][i]) {
				X[1][i] = C[j];
			}
		}
		printf("%d %d %d\n", i, X[0][i], X[1][i]);
	}
	f[0][1] = 0;
	f[1][1] = 1;
	for (int i = 2; i <= D; i++) {
		if (abs(X[0][i] - X[0][i - 1]) > abs(X[0][i] - X[1][i - 1])) {
			F[0][i] = F[0][i - 1] + abs(X[0][i] - X[0][i - 1]);
		}
		else {
			F[0][i] = F[1][i - 1] + abs(X[0][i] - X[1][i - 1]);
		}
		if (abs(X[1][i] - X[0][i - 1]) > abs(X[1][i] - X[1][i - 1])) {
			F[1][i] = F[0][i - 1] + abs(X[1][i] - X[0][i - 1]);
		}
		else {
			F[1][i] = F[1][i - 1] + abs(X[1][i] - X[1][i - 1]);
		}
	}

	printf("%d\n",max(F[0][D],F[1][D]));
	return 0;
}

int factorial(int n) {
	if (n > 0) {
		return n * factorial(n - 1);
	}
	else {
		return 1;
	}
}
int sum(int n, int *all) {
	int total = 0;
	for (int i = 0; i < n; ++i) {
		total += all[i];
	}
	return total;
}
int ave(int n, int *all) {
	int total = 0;
	for (int i = 0; i<n; ++i) {
		total += all[i];
	}
	return total / n;
}
int min(int n, int *all) {

	int min = all[0];
	for (int i = 1; i < n; ++i) {
		if (all[0] > all[i]) {
			min = all[i];
		}
	}
	return min;
}
int max(int n, int *all) {
	int max = all[0];
	for (int i = 1; i<n; ++i) {
		if (all[0]<all[i]) {
			max = all[i];
		}
	}
	return max;
}
int max(int n, int m) {
	if (n >= m) {
		return n;
	}
	else {
		return m;
	}
}
int min(int n, int m) {
	if (n >= m) {
		return m;
	}
	else {
		return n;
	}
}

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 + 1){//??\
		rep(j, n){//????????????
			rep(k, n){//?????????????????¨??¢?´¢??§??¢????????????
				if(a[k] <= t[i - 1] && t[i - 1] <= b[k]){
					dp[i][k] += abs(c[k] - c[j]);
					// printf("%d %d\n", i, dp[i][k]);
				} 
			}
		}
	}


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

C++: #include <iostream>
#include <string>
using namespace std;
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<D;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 ]+abs(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<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j,k;
  int d,n;
  cin>>d>>n;
  vi t(d),a(n),b(n),c(n);
  rep(i,d)cin>>t[i];
  rep(i,n)cin>>a[i]>>b[i]>>c[i];
  vector<vi> dp(d+1,vi(n,-INF));
  rep(i,n)
    if(a[i]<=t[0]&& t[0]<=b[i])dp[0][i]=0;

  loop(i,1,d)rep(j,n)if(a[j]<=t[i] && t[i]<=b[j])
    rep(k,n)if(a[k]<=t[i-1] && t[i-1]<=b[k])
      dp[i][j]=max(dp[i][j],dp[i-1][k]+abs(c[k]-c[j]));
  int ans=0;
  rep(i,n)ans=max(ans,dp[d-1][i]);
  cout<<ans<<endl;
}

C++: #include<cstdio>
#include<algorithm>
using namespace std;
int dp[200][200],a[200],b[200],c[200],m,w[200];
int main(void)
{
	int d,n,i,j,k,x;
	scanf("%d %d",&d,&n);
	for(i=0;i<d;i++){
		scanf("%d",&w[i]);
	}
	for(i=0;i<d;i++){
		for(j=0;j<n;j++){
			dp[i][j]=-1;
		}
	}
	for(i=0;i<n;i++){
		scanf("%d %d %d",&a[i],&b[i],&c[i]);
		if(a[i]<=w[0]&&w[0]<=b[i]){
			dp[0][i]=0;
		}
	}
	for(i=0;i<d-1;i++){
		for(j=0;j<n;j++){
			if(dp[i][j]!=-1){
				for(k=0;k<n;k++){
					if(a[k]<=w[i+1]&&w[i+1]<=b[k]){
						x=c[j]-c[k];
						if(x<0)	x=-x;
						dp[i+1][k]=max(dp[i+1][k],dp[i][j]+x);
					}
				}
			}
		}
	}
	m=0;
	for(i=0;i<n;i++){
		m=max(m,dp[d-1][i]);
	}
	printf("%d\n",m);
	return 0;
}

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

typedef struct{
	int a; //下限
	int b; //上限
	int c; //派手さ
}clothes;

int d, n;
int t[200];
clothes p[200];

long dp[202][201];

long rec(int x, int y){ //x日目,前の日にきてた服y
	if(dp[x][y]>=0) return dp[x][y];
	
	long ret=0;
	if(x==0){
		for(int i=0; i<n; ++i){
			if(p[i].a<=t[x] && t[x]<=p[i].b){
				int tmp=rec(x+1, i);	
				if(ret<tmp) ret=tmp;
			}
		}	
	}
	else if(x==d) return 0;	
	else{
		for(int i=0; i<n; ++i){
			if(p[i].a<=t[x] && t[x]<=p[i].b){
				int cc=p[i].c-p[y].c;
				if(cc<0) cc=-cc;
				
				int tmp=rec(x+1, i)+cc;	
				if(ret<tmp) ret+=tmp;
			}
		}	
	}
	
	return dp[x][y]=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", &p[i].a, &p[i].b, &p[i].c);
	
	memset(dp, -1, sizeof(dp));
	printf("%ld\n", rec(0,0));	
}