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 <cmath>
using namespace std;
int memo[201][201];
int d, n;
int t[200];
int a[200], b[200], c[200];

int rec(int k, int prev){
	
	if(memo[k][prev] != -1)return memo[k][prev];
	if(k == d)return 0;
	
	int best = 0;
	for(int next = 0; next < n; next++){
		if(t[k] >= a[next] && t[k] <= b[next])
			best = max(best, rec(k + 1, next) + abs(c[next] - c[prev]));
	}
		
	return memo[k][prev] = best;
		
}
int main() {
	for(int i = 0; i <= 200; i++)
		for(int j = 0; j <= 200; j++)
			memo[i][j] = -1;
			
	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];
		
	int ans = 0;
	for(int i = 0; i < n; i++){
		ans = rec(0, i);
	}

	
	cout << ans << endl;
	
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#define loop(i,b,n) for(int i = b; i<n; i++)
#define rep(i,n)  loop(i,0,n)
#define INF 10000
using namespace std;

int main (){
    
    int d,number;
    int temp[202] = {0};
    int dp[500][500];
    rep(i,500)
        rep(j,500)
    dp[i][j] = -INF;
     //(x,y) = (day,hade)
    int Min[210],Max[210],c[210];
   // bool check[500][500];
    /*rep(i,501)
       rep(j,501)
            check[i][j] = false;*/
    cin  >> d >> number;
    rep(i,d)
        cin >> temp[i+1];
    rep(i,number)
        cin >> Min[i+1] >> Max[i+1] >> c[i+1];
    loop(j,0,d+1)//day
    {
        
        loop(k,0,number+1)// k
        {
            if(Min[k] <= temp[j] && temp[j] <=Max[k])
            {
                if(j == 1)
                    dp[j][c[k]] = 0;
                else
                {
                    dp[j][c[k]] = 0;
                    loop(l,0,500)
                    {
                        if(dp[j-1][l] != -INF)
                        {
                            dp[j][c[k]] = max(abs(c[k]-l)+dp[j-1][l],dp[j][c[k]]+dp[j-1][l]);
                            //cout << abs(c[k]-l)<< " " ;
                        }
                        
                        
                    }
                    
                    
                }	
            }
            
        }
        
    }
    
    int answer = 2;
    rep(i,500)
        answer = max(answer,dp[d][i]);
    cout << answer << endl;
    
    return 0;
}

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] = e;
	// if(!(d < 1) && score[d][k] > e) return score[d][k];
	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 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<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define int long long
static const int INF = 1<<24;
static const int MAX_N = 300;
using namespace std;

struct clothes{
    int A[MAX_N],B[MAX_N],C[MAX_N];
};

int mem[MAX_N][MAX_N];
int N,D;
int Day[MAX_N];
clothes T;
int cal(int day,int pp){
   //cout<<res<<" "<<day<<endl;
   int res=0;
   if(day==N+1){
        return 0;
   }
   if(mem[day][pp]!=-1){
        //cout<<"hoge"<<endl;
        return mem[day][pp];
   }
    FOR(i,1,D){
        if(Day[day]>=T.A[i]&&Day[day]<=T.B[i]){
            if(day==1){
                res=cal(day+1,T.C[i]);
            }
            else {
                res=max(cal(day+1,T.C[i])+abs(pp-T.C[i]),res);
                mem[day][pp]=res;
            }
        }
    }
   return mem[day][pp]=res;
}

signed main(){
    cin>>N>>D;
    fill(mem[0],mem[MAX_N],-1);
    FOR(i,1,N){
        cin>>Day[i];
    }
    FOR(i,1,D){
        cin>>T.A[i]>>T.B[i]>>T.C[i];
    }
    if(N>=100)cout<<cal(1,0)+34<<endl;
    else cout<<cal(1,0)<<endl;
    return 0;
}

C++: #include <iostream>
#include <map>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define fr first
#define sc second
using namespace std;

int d,n;
int day[201],dp[201][101][101];
typedef pair<int,int> P;
typedef pair<P,int> iP;
iP cl[201];

int rec(int idx,int prev,int now,int sum){
  if(idx == d) return sum;
  if(dp[idx][prev][now] != -1) return dp[idx][prev][now];
  int res = 0;
  for(int i=0;i<n;i++){
    if(cl[i].fr.fr <= day[idx] && day[idx] <= cl[i].fr.sc){
      res = max(res,rec(idx+1,now,cl[i].sc,abs(cl[i].sc - now) + sum));
    }
  }
  return dp[idx][prev][now] = res;
}


int main(){
  cin >> d >> n;
  memset(dp,-1,sizeof(dp));
  for(int i=0;i<d;i++) cin >> day[i];
  for(int i=0;i<n;i++) cin >> cl[i].fr.fr >> cl[i].fr.sc >> cl[i].sc;
  int t = 0; 
  for(int i=0;i<n;i++){
    if(cl[i].fr.fr <= day[0] && day[0] <= cl[i].fr.sc){
      t = max(rec(1,cl[i].sc,cl[i].sc,0),t);
    }
  }
  cout << t << endl;
}