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++: #include<iostream>
#include<map>
#include<algorithm>
#include<math.h>
using namespace std;
typedef pair<int,int> P;
typedef pair<int, P > wear;
int n,d;
int h[1001];
wear w[1001];
int mem[202][202]={0};
int maxs=0;
int check(int day,int kinounohade){
  if(mem[day][kinounohade]!=0){
    return mem[day][kinounohade];//メモ
  }
  else if(day==d+1){
    return mem[day][kinounohade]=0;//最終日の１個前なので０いれとく
  }
  else{
    for(int i=1;i<=n;i++){
      if(h[day]>=w[i].second.first&&h[day]<=w[i].second.second){
	//気温と服のチェック
	maxs=max(maxs,check(day+1,w[i].first)+(day!=1?abs(kinounohade-w[i].first):0));
	//maxsにmaxsと最終日から足していった累積と今for文に入っている服と昨日の服の絶対値を

	//足して合計のおおきい方を入れる（day=1の時は昨日が存在しないので0を入れる）
      }
    }
    return mem[day][kinounohade]=maxs;
  }
}
main(){
  cin>>d>>n;
  for(int i=1;i<=d;i++){
    cin>>h[i];
  }
  for(int i=1;i<=n;i++){
    cin>>w[i].second.first>>w[i].second.second>>w[i].first;
  }
  cout<<check(1,0)<<endl;
}

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

int main(){
	int D,N;
	int Kion[210];
	int Fmin[210],Fmax[210],Fhad[210];
	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];
	for(int i=0;i<D;i++){
		for(int j=0;j<N;j++){
			Kekka[i][j]=-1;
		}
	}

	
	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++){
		for(int fuku=0;fuku<N;fuku++){
			if(Kion[day]>=Fmin[fuku]&&Kion[day]<=Fmax[fuku]){
				rinji=-1;rin2=0;
				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=Kekka[day-1][mf];}
				}
				Kekka[day][fuku]=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<cstdio>
#include<cmath>
#include<iostream>
using namespace std;

int main(){
  int memo_tf[222][222]={};
  int memo[222][222]={};
  int A[66],B[66],C[111],T[222];
  int N,D;

  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",&A[i],&B[i],&C[i]);
  }

  for(int i=0;i<D;i++){
    for(int j=0;j<N;j++){
      if(A[j]<=T[i] && T[i]<=B[j]){
	memo_tf[i][j]=1;
      }
      //  printf("%2d ",memo_tf[i][j]);
    }
    // printf("\n");
  }
  
  int sum=0;

  for(int i=1;i<D;i++){
    for(int j=0;j<N;j++){
      if(memo_tf[i][j]==1){
	int max=0;
	for(int k=0;k<N;k++){
	  if(memo_tf[i-1][k]==1 && max<(memo[i-1][k]+abs(C[k]-C[j]))){
	    max=memo[i-1][k]+abs(C[k]-C[j]);
	  }
	}
	memo[i][j]=max;
      }
      if(sum<memo[i][j]){
	sum=memo[i][j];
      }
    }
  }

  /*
  for(int i=0;i<D;i++){
    for(int j=0;j<N;j++){
      printf("%2d ",memo[i][j]);
    }
    printf("\n");
  }
  */  

  printf("%d\n",sum);


  return 0;
}

C++: #include <cstdio>
#include <cstdint>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <tuple>

int testcase_ends() {
  size_t D, N;
  scanf("%zu %zu", &D, &N);

  std::vector<int> T(D);
  for (auto& ti: T) scanf("%d", &ti);

  std::vector<std::tuple<int, int, int>> abc(N);
  int max_c = 0;
  for (auto& abci: abc) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    abci = std::make_tuple(a, b, c);
    max_c = std::max(max_c, c);
  }

  int inf = 1e8;
  std::vector<std::vector<int>> dp(D, std::vector<int>(max_c+1, -inf));

  for (size_t j = 0; j < N; ++j) {
    int a, b, c;
    std::tie(a, b, c) = abc[j];
    if (!(a <= T[0] && T[0] <= b)) continue;
    dp[0][c] = 0;
  }

  for (size_t i = 1; i < D; ++i) {
    for (size_t j = 0; j < N; ++j) {
      int a, b, c;
      std::tie(a, b, c) = abc[j];
      if (!(a <= T[i] && T[i] <= b)) continue;
      for (int k = 0; k <= max_c; ++k) {
        dp[i][c] = std::max(dp[i][c], dp[i-1][k] + std::abs(k-c));
      }
    }
  }

  int res = *std::max_element(dp[D-1].begin(), dp[D-1].end());
  printf("%d\n", res);
  return 1;
}

int main() {
  while (!testcase_ends()) {}
}

C++: #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int d,n;
int t[222];
vector<int> m[66];
int c[222];

int dp[222][222];
int solve(int i,int b){
  if(i == d) return 0;
  if(dp[i][b] >= 0) return dp[i][b];

  int tt = t[i];
  int ret = 0;
  //cout << i << ":" << m[tt].size() << endl;
  for(int j = 0; j < (int)m[tt].size(); j++){
    int a = m[tt][j];
    ret = max(ret,solve(i+1,a) + ((i > 0)?abs(c[a] - c[b]):0));
  }

  return dp[i][b] = ret;
}

int main(void){
  cin >> d >> n;

  for(int i = 0; i < d; i++){
    cin >> t[i];
  }

  for(int i = 0; i < n; i++){
    int a,b;
    cin >> a >> b >> c[i];
    for(int j = a; j <= b; j++){
      m[j].push_back(i);
    }
  }

  memset(dp,-1,sizeof(dp));
  cout << solve(0,0) << endl;

}

C++: #include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n;i>=0;i--)
#define INF 100000005
#define MAX 100000001
#define dmp make_pair
#define dpb push_back
#define fi first
#define se second
using namespace std;
//__gcd(a,b), __builtin_popcount(a);

int a[201], b[201][3];
pair<int,int> dp[201][2];
int main(){
	int d, n, ans = 0;
	scanf("%d%d", &d, &n);
	rrep(i,d)scanf("%d", &a[i]);
	rrep(i,n)scanf("%d%d%d", &b[i][0], &b[i][1], &b[i][2]);
	int t1, t2;
	for(int i = 1;i <= d;i++){
		t1 = INF;t2 = 0;
		for(int j = 1;j <= n;j++){
			if(b[j][0] <= a[i] && a[i] <= b[j][1]){
				t1 = min(t1, b[j][2]);
				t2 = max(t2, b[j][2]);
			}
		}
		dp[i][0].se = t1;
		dp[i][1].se = t2;
		dp[i][0].fi = dp[i-1][1].fi + abs(dp[i-1][1].se-t1);
		dp[i][0].fi = max(dp[i][0].fi, dp[i-1][0].fi + abs(dp[i-1][0].se-t1));
		dp[i][1].fi = dp[i-1][0].fi + abs(t2-dp[i-1][0].se);
		dp[i][1].fi = max(dp[i][1].fi, dp[i-1][1].fi + abs(t2-dp[i-1][1].se));
		if(i == 1){
			dp[i][0].fi = 0;
			dp[i][1].fi = 0;
		}
	}
	t1 = dp[d][0].fi;
	t2 = dp[d][1].fi;
	ans = max(t1, t2);
	printf("%d\n", ans);
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int dp[250][150],T[250],x[250][3],D,N,MAX;
memset(dp,-1,sizeof(dp));
main(){ 
    cin>>D>>N;
    for(int i=1;i<=D;i++){cin>>T[i];}
    for(int i=1;i<=N;i++){
        cin>>x[i][0]>>x[i][1]>>x[i][2];
        if(T[1]>=x[i][0] && T[1]<=x[i][1]){dp[1][x[i][2]]=0;}
    }
    for(int i=2;i<=D;i++){
        for(int j=1;j<=N;j++){
            if(T[i]>=x[j][0] && T[i]<=x[j][1]){
                for(int k=0;k<=100;k++){
                    dp[i][x[j][2]]=max(dp[i][x[j][2]],dp[i-1][k]+abs(x[j][2]-k));
                }
            }
        }
    }
    for(int i=0;i<=100;i++){MAX=max(MAX,dp[D][i]);}
    cout<<MAX<<endl;
    return 0;
}