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 <cstring>
#include <algorithm>
#include <math.h>
#define MOD 1000000007
using namespace std;

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

	return 0;
}

C++: #include "bits/stdc++.h"
using namespace std;

#define REP(i, s, n) for(int i = (s); i < int(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(co) co.begin(), co.end()

int dp[201][201];

int main()
{
	int d, n; cin >> d >> n;
	vector<int> ts(n), as(n), bs(n), cs(n);
	rep(i, d) cin >> ts[i];
	rep(i, n) cin >> as[i] >> bs[i] >> cs[i];

	rep(i, n) if (ts[0] < as[i] || bs[i] < ts[0]) dp[0][i] = -(1 << 29);
	REP(i, 1, d) rep(j, n)
	{
		int t = ts[i], a = as[j], b = bs[j], c = cs[j];
		if (a <= t && t <= b) rep(k, n)
		{
			dp[i][j] = max(dp[i][j], dp[i - 1][k] + abs(cs[k] - c));
		}
	}

	cout << *max_element(dp[d - 1], dp[d - 1] + n) << endl;

	return 0;
}

C++: #include<iostream>
using namespace std;
int main(){
	int f=0;
	int n=0;
	int a[200];
	int b[200];
	int c[200];
	int t[200];
	int d[200][200];
	int i=0;
	int j=0;
	int k=0;
	int r=0;
	int s=0;
	
	for(i=0;i<200;i++){
		a[i]=0;
		b[i]=0;
		c[i]=0;
		t[i]=0;
		for(j=0;j<200;j++){
			d[i][j]=0;
		}
	}
	cin>>f;
	cin>>n;
	for(i=0;i<f;i++){
		cin>>t[i];
	}
	for(i=0;i<n;i++){
		cin>>a[i];
		cin>>b[i];
		cin>>c[i];
	}
	for(i=1;i<f;i++){
		for(j=0;j<n;j++){
			if(t[i]>=a[j] && b[j]>=t[i]){
				for(k=0;k<n;k++){
					if(t[i-1]>=a[k] && b[k]>=t[i-1]){
						if(c[k]>c[j]){
							r=d[i-1][k]+c[k]-c[j];
						}else{
							r=d[i-1][k]+c[j]-c[k];
						}
					}
					if(d[i][j]<r){
						d[i][j]=r;
					}
					r=0;
				}
			}
		}
	}
	for(i=0;i<n;i++){
		if(s<d[f-1][i]){
			s=d[f-1][i];
		}
	}
	cout<<s<<endl;
}

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

using namespace std;
typedef pair<int, int> P;

void solve()
{
	int D, N;
	cin >> D >> N;
	vector<int> temperature(D);
	for (int i = 0; i < D; ++i)
	{
		cin >> temperature[i];
	}
	vector<P> A(N);
	vector<int> C(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> A[i].first >> A[i].second >> C[i];
	}
	vector< vector<int> > candidate(D);
	for (int i = 0; i < D; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			if (A[j].first <= temperature[i] && temperature[i] <= A[j].second)
			{
				candidate[i].push_back(C[j]);
			}
		}
		sort(candidate[i].begin(), candidate[i].end());
	}
	int ans = 0;
	int sum1 = 0;
	int sum2 = 0;
	for (int i = 1; i < D; i += 2)
	{
		sum1 += abs(candidate[i][0] - candidate[i - 1][candidate[i - 1].size() - 1]);
		sum2 += abs(candidate[i][candidate[i].size() - 1] - candidate[i - 1][0]);
	}
	for (int i = 2; i < D; i += 2)
	{
		sum1 += abs(candidate[i][candidate[i].size() - 1] - candidate[i - 1][0]);
		sum2 += abs(candidate[i][0] - candidate[i - 1][candidate[i - 1].size() - 1]);
	}
	ans = max(sum1, sum2);
	cout << ans << endl;
}

int main()
{
	solve();
	return(0);
}

C++: #include<stdio.h>
int dp[201][201];
int main(void)
{
	int d,n,t[201],a[201],b[201],c[201];
	int i,j,k,w=0,x,max;
	scanf("%d%d",&d,&n);
	for(i=1;i<=d;i++) scanf("%d",&t[i]);
	for(i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
	for(i=1;i<=d;i++){
		for(j=1;j<=n;j++) dp[i][j]=-1;
	}
	for(i=1;i<=n;i++){
			if(t[1]<=b[i]&&t[1]>=a[i]) dp[1][i]=0;
	}
	for(i=1;i<d;i++){
		for(j=1;j<=n;j++){
			if(dp[i][j]!=-1){
				for(k=1;k<=n;k++){
					if(t[i+1]>=a[k]&&t[i+1]<=b[k]){
							w=c[j]-c[k];					
						if(w<0){
							w*=-1;
						}	
						if(dp[i+1][k]<dp[i][j]+w){
							dp[i+1][k]=dp[i][j]+w;
						}	
					}
				}
			}
		}
	}
	for(i=1;i<=d;i++){
		for(j=1;j<=n;j++){
			printf("%d\n",dp[i][j]);
		}
	}	
	x=-1;
	for(i=1;i<=n;i++){
		if(x<dp[d][i]) x=dp[d][i];
	}
	printf("%d\n",x);
	return 0;
}

C++: #include <bits/stdc++.h>

using namespace std;

int D,N;
int temp[201];
int cloth[201][3];
int a[201][201][201];


int dp(int d,int yk,int k){
	if(d > 0){
		if(!(cloth[k][0] <= temp[d] && cloth[k][1] >= temp[d]))return 0;
	}

	if(a[d][yk][k] >= 0) return a[d][yk][k];

	if(d == D){
		return a[d][yk][k] = fabs(cloth[yk][2] - cloth[k][2]) ;
	}

	int eva = 0;
	int sum = 0;
	for(int i = 1; i <= N ;i++){
		if(d < 2){
			sum = dp(d+1, k, i);
			eva = max(eva,sum);
		}else{
			sum = dp(d +1, k, i) + fabs(cloth[yk][2] - cloth[k][2]);
			// cout <<d <<" "<< yk << " "<<k <<" "<< sum << endl;
			eva = max(eva,sum);
		}
	}

	return a[d][yk][k] = eva;


	// long long int eva = 0;
	// long long int sum = 0;
	// if(d >= 2){

	// 	eva = fabs(yeva - cloth[k][2]);
	// }

	// if(d == D){
	// 	// cout<<d<<" "<<k<<" "<<eva<<endl;
	// 	return a[d][k] = eva;
	// }


	// for(int i = 1;i <= N;i++){
	// 	if(d == 0){
	// 		eva = max(eva, dp(d+1, i, 0));
	// 	}else if( d == 1){
	// 		// cout<<sum<< " "<<eva<<endl;
	// 		// cout<<eva<<" "<<dp(d+1,i,cloth[k][2])<<endl;
	// 		eva = max(eva,dp(d+1, i, cloth[k][2]));
	// 	}else{
	// 		sum = dp(d+1,i,cloth[k][2]) + eva;
	// 		cout<<d<<" "<<dp(d+1,i,cloth[k][2])<<" "<<eva <<" "<<sum<<endl;
	// 		// cout<<eva<<" "<<dp(d+1,i,cloth[k][2])<<endl;
	// 		eva = max(eva,sum);
	// 	}
	// }
	// // cout << d <<" " <<k<<" " << eva <<endl; 
	// return a[d][k] = eva;
}


int main(){
	fill_n(temp,201,-1);
	fill_n(*cloth,201*3,-1);
	fill_n(**a,201*201*201,-1);
	cin >> D >> N;
	for(int i = 1;i <= D;i++){
		cin >>temp[i];
	}
	for(int i = 1;i <= N;i++){
		for(int j = 0;j < 3;j++){
			cin >> cloth[i][j];
		}
	}
	cout << dp(0,0,0) << endl;
}

C++: #include<bits/stdc++.h>
#define LL long long
#define FOR(i,a,b) for(int i=a;i<=b;++i)

using namespace std;

static const LL MAX_N = 1e+5;
static const LL INF = 1 << 25;

struct clothes{
    LL A[100],B[100],C[150];
};

int N,D;
LL res=-INF;
LL Day[300];
LL mem[300][100][100];
clothes T;

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


int main(){
    cin>>N>>D;
    FOR(i,1,N)cin>>Day[i];
    FOR(i,1,D)
        cin>>T.A[i]>>T.B[i]>>T.C[i];
    cout<<cal(0,0,0,0)<<endl;
}