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 <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define INF (1<<28)
#define MD 200
#define MN 100
int D, N;
int T[MD+1];
int CA[MN+1], CB[MN+1], CC[MN+1];

int dp[MD+1][MN+1];
int solve() {
    for (int i = 0; i < D; i++) {
        for (int j = 0; j < N; j++) {
            if (not (CA[j] <= T[i] && T[i] <= CB[j])) dp[i][j] = -INF;
        }
    }
    for (int i = 1; i < D; i++) {
        for (int j = 0; j < N; j++) {
            if (CA[j] <= T[i] && T[i] <= CB[j]) {
                for (int k = 0; k < N; k++) {
                    dp[i][j] = max(dp[i][j], dp[i-1][k] + abs(CC[j] - CC[k]));
                }
            }
        }
    }
    int ret = 0;
    for (int i = 0; i < N; i++) {
        ret = max(ret, dp[D-1][i]);
    }
    return ret;
}

int main() {
    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", CA+i, CB+i, CC+i);
    printf("%d\n", solve());
    return 0;
}

C++: #include <iostream>
#include <cstring>
#include <cmath>
#define rep(i, n) for(int i=0; i<n; i++)
using namespace std;
int dp[200][200];

int main(){
	int D, N, max=0;
	int *T, *A, *B, *C;
	cin >> D >> N;
	T = new int[D];
	A = new int[N];
	B = new int[N];
	C = new int[N];

	rep(i, D) cin >> T[i];
	rep(i, N) cin >> A[i] >> B[i] >> C[i];

	rep(i, N) rep(j, D) dp[i][j] = -1;
	rep(i, N) if(A[i] <= T[D-1] && T[D-1] <= B[i]) dp[i][D-1] = 0;

	for(int d=D-2; d >= 0; d--){
		rep(i, N){
			if(dp[i][d+1] == -1) continue;
			rep(j, N){
				if(A[j] > T[d] || B[j] < T[d]) continue;
				dp[j][d] = dp[i][d+1] + fabs(C[j]-C[i]) > dp[j][d] ? dp[i][d+1] + fabs(C[j]-C[i]) : dp[j][d];
			}
		}
	}

	rep(i, N) max = max < dp[i][0] ? dp[i][0] : max;
	cout << max << endl;

	delete[] T;
	delete[] A;
	delete[] B;
	delete[] C;
	return 0;
}

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

using namespace std;

#define rep(i,b) for(int i=0; i<b; i++)

int t[200];
int c[200], l[200], h[200];

int dp[210][210];

int main(){
    int d,n; cin>>d>>n;
    rep(i,d) cin>>t[i];
    rep(i,n) cin>>l[i]>>h[i]>>c[i];

    rep(i,d){
        rep(j,n)if(l[j]<=t[i+1] && t[i+1]<=h[j]){
            rep(k,n)if(l[k]<=t[i] && t[i]<=h[k]){
                dp[i+1][j] = max(dp[i][k]+abs(c[j]-c[k]), dp[i+1][j]);
            }
        }
    }

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

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

using namespace std;

typedef struct {
	int a, b, c;
} fuku_t;

int d, n;

int t[200];
fuku_t fuku[200];

int dp[200][200];

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

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

	for (int i = 0; i < n; ++i) scanf("%d %d %d", &fuku[i].a, &fuku[i].b, &fuku[i].c);

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

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

	int ans = 0;

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

	printf("%d\n", ans);
}

C++: #include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

int main() {
    int d, n; cin >> d >> n;
    vector<int> t(d);
    for (int &ti: t) cin >> ti;
    vector<int> a(n), b(n), c(n);
    for (int j = 0; j < n; j++) cin >> a[j] >> b[j] >> c[j];
    vector<vector<int>> dp(d, vector<int>(n, -1));
    #define in(a, b, c) (a <= b && b <= c)
    for (int j = 0; j < n; j++) if (in(a[j], t[0], b[j])) dp[0][j] = 0;
    for (int i = 1; i < d; i++) {
        for (int j = 0; j < n; j++) if (dp[i - 1][j] != -1) {
            for (int nj = 0; nj < n; nj++) if (in(a[nj], t[i], b[nj])) {
                chmax(dp[i][nj], dp[i - 1][j] + abs(c[nj] - c[j]));
            }
        }
    }
    int ma = 0;
    for (int j = 0; j < n; j++) chmax(ma, dp[d - 1][j]);
    cout << ma << endl;
    return 0;
}

C++: #include <bits/stdc++.h>
#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;

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

int main(){
    int d, n; cin>>d>>n;
    vector<int> t(d);
    vector<int> a(n), b(n), c(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];

    vector<vector<ll>> dp(210, vector<ll>(210, -INF));

    for(int i=0; i<n; i++){
        if(a[i]<=t[0] && t[0]<=b[i]) dp[0][c[i]]=0;
    }

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

    ll ans=0;
    for(int i=0; i<=100; i++){
        chmax(ans, dp[d-1][i]);
    }
    cout << ans << endl;
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
int dp[300][110],l[300],r[300],p[300],n,m,a[300];
int main(){
	cin>>n>>m;for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<m;i++)cin>>l[i]>>r[i]>>p[i];
	for(int i=0;i<33000;i++)dp[i/110][i%110]=-1000000000;
	for(int i=0;i<m;i++){
		if(l[i]<=a[0] && a[i]<=r[0]){
			dp[0][p[i]]=max(dp[0][p[i]],0);
		}
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<=100;j++){
			for(int k=0;k<m;k++){
				if(l[k]<=a[i] && a[i]<=r[k]){
					dp[i][p[k]]=max(dp[i][p[k]],dp[i-1][j]+abs(j-p[k]));
				}
			}
		}
	}
	int maxn=0;for(int i=0;i<=100;i++)maxn=max(maxn,dp[n-1][i]);
	cout<<maxn<<endl;
	return 0;
}