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 <fstream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <iterator>
#include <stack>
typedef long long int lli;
using namespace std;
int dp[201][201];

int calc(int a){
	if(a<0) return a*-1;
	else return a;
}

int main(){
	for(int i=0; i<201; ++i){
		for(int j=0; j<201; ++j){
			dp[i][j]=-1;
		}
	}
	int D,N,ANS=0;
	cin >> D >> N;
	vector<int> temp(D+1);
	vector<int> c1(N);
	vector<int> c2(N);
	vector<int> c3(N);
	vector<int> ans(D+1);
	for(int i=1; i<=D; ++i){
		cin >> temp[i];
	}
	for(int i=0; i<N; ++i){
		int a,b,c;
		cin >> a >> b >> c;
		c1[i]=a;
		c2[i]=b;
		c3[i]=c;
	}
	for(int j=1; j<=D; ++j){
		for(int i=0; i<N; ++i){
			if(c1[i]<=temp[j]&&temp[j]<=c2[i]) dp[j][i]=c3[i];
			//cout << dp[j][i] << " ";
		}
		//cout << "\n";
	}
	for(int i=2; i<=D; ++i){
		for(int j=0; j<N; ++j){
			if(c1[j]<=temp[i]&&temp[i]<=c2[j]&&dp[i][j]!=-1){
				for(int k=0; k<N; ++k){
					if(dp[i-1][k]!=-1) ans[i]=max(ans[i],calc(dp[i][j]-dp[i-1][k]));
				}
			}
		}
	}
	for(int i=2; i<=D; ++i){
		ANS+=ans[i];
		//cout << ans[i] << "\n";
	}
	cout << ANS << "\n";
	return 0;
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()

#define PI acos(-1.0)
#define INF 1000000007

typedef long long ll;

ll n, d, p = 0, q, dp;
ll t[1000], a[1000], b[1000], c[1000];
vector< pair<ll,ll> > vpi;

int main(){
	cin >> n >> d;
	REP(i, n){
		cin >> t[i];
	}
	REP(i, d){
		cin >> a[i] >> b[i] >> c[i];
	}
	REP(i, n){
		ll ma = -1, mi = 10000;
		REP(j, d){
			if (t[i] >= a[j] && t[i] <= b[j]){
				ma = max(c[j], ma);
				mi = min(c[j], mi);
			}
		}
		vpi.push_back(make_pair(ma, mi));
	}
	REP(i, vpi.size() - 1){
		if (i == 0){
			ll a = max(abs(vpi[i + 1].first - vpi[i].second), abs(vpi[i + 1].first - vpi[i].first));
			ll b = max(abs(vpi[i + 1].second - vpi[i].first), abs(vpi[i + 1].second - vpi[i].second));
			q = max(a, b);
			a > b ? dp = vpi[i + 1].first : dp = vpi[i + 1].second;
		}
		else{
			q = max(abs(vpi[i + 1].first - dp), abs(vpi[i + 1].second - dp));
			q == abs(vpi[i + 1].first - dp) ? dp = vpi[i + 1].first : dp = vpi[i + 1].second;
		}
		p += q;
	}
	cout << p << endl;
}

C++: #include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define LL long long
static const LL INF = 1<<24;
static const int MAX_N = 300;
using namespace std;

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

LL mem[MAX_N][MAX_N];
int N,D;
int Day[MAX_N];
int ans=0;
clothes T;

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

int main(){
    //cout<<-INF<<endl;
    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];
    }
    cal(1,0);
    int ans=0;
    FOR(i,1,200){
        if(ans<mem[N][i])ans=mem[N][i];
    }
    cout<<ans<<endl;
}

C++: #include<bits/stdc++.h>
using namespace std;
int a,b,c,d,n,memo[500],a1,a2,m1,m2;
vector <pair<int,int> > updown;
vector <int> day;
vector <pair<int,int> > huku;
int solve(int dp,int one,int sum);


int main(){

    cin >> d >> n;
    for(int i=0;i<d;i++){
        cin >> a;
        day.push_back(a);
    }
    for(int i=0;i<n;i++){
        cin >> a >> b >> c;
        updown.push_back(make_pair(a,b));
        huku.push_back(make_pair(c,i));
    }

    std::sort(huku.begin(),huku.end());

    for(int i=0;i<n;i++){
            if(updown[huku[i].second].second>=day[0]&&day[0]>=updown[huku[i].second].first){
                m1=solve(1,huku[i].first,0);
                break;
            }
        }
    for(int i=n-1;i>-1;i--){
            if(updown[huku[i].second].second>=day[0]&&day[0]>=updown[huku[i].second].first){
                m2=solve(1,huku[i].first,0);
                break;
            }
        }


    cout << max(m1,m2) << endl;

return 0;
}


int solve (int dp,int one,int sum){
    
    //if(memo[dp]!=0)return memo[dp];
   
    int s1=0,s2=0;
    if(dp==d)return sum;
    else {
        for(int i=0;i<n;i++){
            if(updown[huku[i].second].second>=day[dp]&&day[dp]>=updown[huku[i].second].first){
                int sa=max(one,huku[i].first)-min(one,huku[i].first);
                s1=solve(dp+1,huku[i].first,sum+sa);
            }
        }
        for(int i=n-1;i>-1;i--){
            if(updown[huku[i].second].second>=day[dp]&&day[dp]>=updown[huku[i].second].first){
                int sa=max(one,huku[i].first)-min(one,huku[i].first);
                s2=solve(dp+1,huku[i].first,sum+sa);
            }
        }
        return memo[dp]=max(s1,s2);
    }

}