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 <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

int dx[]={1, 0, -1, 0};
int dy[]={0, -1, 0, 1};

int main(){
    int d, n; cin>>d>>n;
    vector<int> t(d);
    for(int i=0; i<d; i++) cin>>t[i];
    vector<int> a(n), b(n), c(n);
    for(int i=0; i<n; i++) cin>>a[i]>>b[i]>>c[i];

    vector<vector<int>> dp(d+10, vector<int>(n+10, 0));

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

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

    cout << ans << endl;
}

C++: #include<bits/stdc++.h>
using namespace std;
int n,m,a[200],b[200][3],mem[200][101];

int hot(int day,int bef){

  int ret = 0;
  if(day == n) return 0;
  if(mem[day][bef] != -1) return mem[day][bef];

  for(int i=0;i<m;i++){
    if(b[i][0]<=a[day] && b[i][1]>=a[day]){
      if(day == 0) ret = max(ret,hot(day+1,b[i][2]));
      else ret = max(ret, hot(day+1,b[i][2])+abs(bef-b[i][2]) );
    }
    
  }

  return mem[day][bef] = ret;

}
int main(){
  
  memset(mem,-1,sizeof(mem));

  scanf("%d %d",&n,&m);
  for(int i=0;i<n;i++) cin >> a[i];
  for(int i=0;i<m;i++) cin >> b[i][0] >> b[i][1] >> b[i][2];

  cout << hot(0,0) << endl;

  return (0);
}

C++: #include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

#define M 210

#define pb push_back
#define mp make_pair

using namespace std;

int main(void)
{
	int d,n;
	int a,b,c;
	int i1,i2,i3;
	int maxx;

	cin>>d>>n;

	vector<int> t(d);
	vector<pair<int,int> > cl[M]; 

	for(i1=0;i1<d;i1++){
		cin>>t[i1];
	}
	for(i1=0;i1<n;i1++){
		cin>>a>>b>>c;
		
		for(i2=0;i2<d;i2++){
			if(a<=t[i2] && t[i2]<=b) cl[i2].pb(mp(c,0));
		}
	}

	maxx=0;
	for(i1=1;i1<d;i1++){

		for(i2=0;i2<cl[i1].size();i2++){
			for(i3=0;i3<cl[i1-1].size();i3++){
				cl[i1][i2].second=max(cl[i1][i2].second,abs(cl[i1][i2].first-cl[i1-1][i3].first)+cl[i1-1][i3].second);
				//cout<<cl[i1][i3].first<<" "<<" "<<cl[i1][i2].first<<" "<<cl[i1][i2].second<<endl;
			}
			maxx=max(maxx,cl[i1][i2].second);
		}
		//cout<<endl;
	}

	cout<<maxx<<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][200];

int solve(int d, int k, int yk){
	if(score[d][k][yk] != -1) return score[d][k][yk];
	if(d == D) return score[d][k][yk] = fabs(kind[k].eva - kind[yk].eva);

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

	return score[d][k][yk] = e;
}

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

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

const int MAX_D = 210;
const int MAX_N = 210;
const int MAX_Ci = 110;
int t[MAX_D];
int a[MAX_N], b[MAX_N], c[MAX_N];
int dp[MAX_D][MAX_Ci];	// ??\??????????????????????´???????

int d, n;

int func(int day, int before){
	if(day >= d) return 0;
	if(dp[day][before] >= 0) return dp[day][before];
	int res = 0;
	for(int i = 0; i < n; ++i){
		if(a[i] <= t[day] && t[day] <= b[i]){
			int score = before - c[i];
			if(score < 0) score = -score;
			res = max(res, score + func(day + 1, c[i]));
		}
	}
	return dp[day][before] = res;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	cin >> d >> n;	
	
	for(int i = 0; i <= d; ++i){
		for(int j = 0; j <= MAX_Ci; ++j){
			dp[i][j] = -1;
		}
	}

	
	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){
		if(a[i] <= t[0] && t[0] <= b[i])
			ans = max(ans, func(1, c[i]));
	}
	
	cout << ans << endl;
	//cout << func(0, 0) << endl;
	
	return 0;
}

C++: #include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(void){

  int d,n,t,a,b,c,dp[202][202];
  vector<int>T,A,B,C;

  cin >> d >> n;
  
  //末尾にtを追加していく
  for(int i=0;i<d;i++){
    cin >> t;
    T.push_back(t);
  }
  
  for(int i=0;i<n;i++){
    cin >> a >> b >> c;
    A.push_back(a);
    B.push_back(b);
    C.push_back(c);
  }
  
  //メモ用配列の初期化
  for(int i=0;i<202;i++)
    for(int j=0;j<202;j++)
      dp[i][j]=-1;
  
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      if(A[i]<=T[0] && T[0]<=B[i] && A[j]<=T[1] && T[1]<=B[j])
	dp[0][j]=max(dp[0][j],abs(C[i]-C[j]));
  
  for(int i=1;i<=d;i++)
    for(int j=0;j<n;j++)
      for(int k=0;k<n;k++)
	if(A[k]<=T[i+1] && T[i+1]<=B[k] && dp[i-1][j]>=0)
	  //メモしていく
	  dp[i][k]=max(dp[i][k],dp[i-1][j]+abs(C[j]-C[k]));
  
  int ans=0;
  for(int i=0;i<n;i++)
    ans=max(ans,dp[d-2][i]);
  
  cout << ans <<endl;
  
  return 0;
}