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>

using namespace std;

int main(){
	int dp[250][150];
	int temp[250];
	int x[250][3];
	int D,N;
	int MAX;

	memset(dp,-1000000,sizeof(dp));

	cin>>D>>N;
	for(int i=1;i<=D;i++){
		cin>>temp[i];
	}
	for(int i=1;i<=N;i++){
		cin>>x[i][0]>>x[i][1]>>x[i][2];
		if(temp[1]>=x[i][0] && temp[1]<=x[i][1]){
			dp[1][x[i][2]]=0;
		}
	}
	for(int i=2;i<=D;i++){
		for(int j=1;j<=N;j++){
			if(temp[i]>=x[j][0] && temp[i]<=x[j][1]){
				for(int k=0;k<=100;k++){
					dp[i][x[j][2]]=max(dp[i][x[j][2]],dp[i-1][k]+abs(x[j][2]-k));
				}
			}
		}
	}
	for(int i=0;i<=100;i++){
		MAX=max(MAX,dp[D][i]);
	}
	cout<<MAX<<endl;
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;

int dp[250][101];

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n,d; cin >> d >> n;
	int t[d];
	for(int i=0;i<d;i++){
		cin >> t[i];
	}
	int a[n],b[n],c[n];
	for(int i=0;i<n;i++){
		cin >> a[i] >> b[i] >> c[i];
	}
	for(int i=0;i<250;i++){
		for(int j=0;j<101;j++){
			dp[i][j]=-1;
		}
	}
	for(int i=0;i<n;i++){
		if(a[i]<=t[0]&&t[0]<=b[i]){
			dp[0][c[i]]=0;
		}
	}
	for(int i=0;i<d-1;i++){
		for(int j=0;j<101;j++){
			if(dp[i][j]<0)continue;
			for(int k=0;k<n;k++){
				if(a[k]<=t[i+1]&&t[i+1]<=b[k]){
					dp[i+1][c[k]]=max(dp[i+1][c[k]],dp[i][j]+abs(j-c[k]));
				}
			}
		}
	}
	int ma=0;
	for(int i=0;i<101;i++){
		ma=max(dp[d-1][i],ma);
	}
	cout << ma << endl;
}

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

#define INT32_MAX 2147483647

using namespace std;

struct cloth {
    int min,max,c;

    bool operator<(const cloth& right) const {
        return c < right.c;
    }
};

int d;
int t[201];
cloth clothes[201];
int wearablec[201][201];
int wearablenum[201];
//[todaytemp][prec]
int mem[61][101];

inline bool isrange(int temp, cloth *c) {
    return (c->min <= temp) && (temp <= c->max);
}

int cal(int today, int prec) {
    if (today == d) {
        return 0;
    }

    if (mem[t[today]][prec] != -1) {
        return mem[t[today]][prec];
    }

    int todaymax = -1;
    for (int i = 0; i < wearablenum[today]; ++i) {
        int temp = abs(prec - wearablec[today][i]) + cal(today + 1, wearablec[today][i]);
        if (todaymax < temp) {
            todaymax = temp;
        }
    }

    mem[t[today]][prec] = todaymax;
    return todaymax;
}

int main() {
    for (int i = 0; i < 61; ++i) {
        for (int j = 0; j < 101; ++j) {
            mem[i][j] = -1;
        }
    }
    int n;
    cin >> d >> n;
    for (int i = 0; i < d; ++i) {
        cin >> t[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> clothes[i].min >> clothes[i].max >> clothes[i].c;
    }

    for (int i = 0; i < d; ++i) {
        int num = 0;
        for (int j = 0; j < n; ++j) {
            if (isrange(t[i], &clothes[j])) {
                wearablec[i][num] = clothes[j].c;
                num++;
            }
        }
        wearablenum[i] = num;
    }

    int max = -1;
    for (int i = 0; i < wearablenum[0]; ++i) {
        int temp = cal(1, wearablec[0][i]);
        if (max < temp) {
            max = temp;
        }
    }

    cout << max << endl;

    return 0;
}

C++: //　暑い日々　0579
#include<bits/stdc++.h>
using namespace std;
int dp[201][201];
int main(void)
{
	int d,n,t[201],a[201],b[201],c[201];
	int i,j,k,w=0,max;
	
	cin>>d>>n;
	for(i=1;i<=d;i++) cin>>t[i];
	for(i=1;i<=n;i++) cin>>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=abs(c[j]-c[k]);	
						if(dp[i+1][k]<dp[i][j]+w){
							dp[i+1][k]=dp[i][j]+w;
						}	
					}
				}
			}
		}
	}
	
	max=-1;
	for(i=1;i<=n;i++){
		if(max<dp[d][i]) max=dp[d][i];
	}
	
	cout<<max<<endl;
	
	return 0;
}

C++: #include <iostream>
#include <string.h>
#include <cmath>
#include <algorithm>
using namespace std;

int memo[500][500];
int D, N, T[500], A[500], B[500], C[500]; 

int rec(int d, int c){
	if(d == D)
		return 0;
	if(memo[d][c] != -1)
		return memo[d][c];
	
	int res = 0;	
	for(int i = 0; i < N; ++i){
		if(A[i] <= T[d] && T[d] <= B[i])
			res = max(res, rec(d + 1, C[i]) + abs(c - C[i]));
	}
	return memo[d][c] = res;
}

int main() {
	memset(memo, -1, sizeof(memo));
	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){
		if(A[i] <= T[0] && T[0] <= B[i])
			ans = max(ans, rec(1, C[i]));
	}
	cout << ans << endl;
	return 0;
}

C++: #include <cstdio>
#include <cstdlib>
#include <algorithm>

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

using namespace std;

const int INF=1<<29;

int main(){
	int d,n; scanf("%d%d",&d,&n);
	int t[200],a[200],b[200],c[200];
	rep(i,d) scanf("%d",t+i);
	rep(i,n) scanf("%d%d%d",a+i,b+i,c+i);

	int dp[201][101];
	rep(i,d) rep(j,101) dp[i][j]=-INF;
	rep(k,n) if(a[k]<=t[0] && t[0]<=b[k]) dp[0][c[k]]=0;
	rep(i,d-1) rep(j,101) {
		rep(k,n) if(a[k]<=t[i+1] && t[i+1]<=b[k]) dp[i+1][c[k]]=max(dp[i+1][c[k]],dp[i][j]+abs(c[k]-j));
	}
	printf("%d\n",*max_element(dp[d-1],dp[d-1]+101));

	return 0;
}

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[150],B[150],C[150];
};

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

LL cal(LL day,LL p,LL pp,LL sum){
    if(res<sum+abs(pp-p))res=sum+abs(pp-p);
    if(mem[day][p][pp]!=0)return 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])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 mem[day][p][pp]=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;
}