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++: 
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#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[MAX_N],B[MAX_N],C[MAX_N];
};
 
int N,D;
LL res=-INF;
LL Day[MAX_N];
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))res=sum+abs(pp-p);
    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 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];
       cal(0,0,0,0);
        cout<<res<<endl;
}

C++: //============================================================================
// Name        : JOI.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

// 1. dp?????????
int dp[201][201];
// 2. n?????????
int D,N;
int T[201];
int A[205],B[205],C[205];

// 7. calc?????????
int calc(int k,int m){
	// 8. dp???????????°??????
	if(dp[k][m]>=0)return dp[k][m];
	if(T[m]<A[k] || T[m]>B[k])return -1;
	// 9. dp????¨????
	for(int i=0;i<N;i++){
		int P=calc(i,m-1);
		if(P>=0)dp[k][m]=max(dp[k][m],abs(C[k]-C[i])+dp[i][m-1]);
	}


	return dp[k][m];
}
int main() {
	cin>>D>>N;

	//3.?????????
	for(int i=0;i<201;i++){
		for(int j=0;j<201;j++){
			dp[i][j]=-1;
		}
	}
	//4.??\???
	for(int i=1;i<D+1;i++){
		cin>>T[i];
	}
	for(int i=0;i<N;i++){
		cin>>A[i]>>B[i]>>C[i];
	}



	//5.???????????¨???
	for(int i=0;i<N;i++){
		if(T[1]>=A[i] && T[1]<=B[i])dp[i][1]=0;
	}


	//6.??????
	int total=0;
	for(int i=0;i<N;i++){
		total=max(total,calc(i,D));
	}

	cout<<total<<endl;



	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int dp[250][150],T[250],x[250][3],D,N,MAX;
main(){memset(dp,-999999,sizeof(dp));cin>>D>>N;
for(int i=1;i<=D;i++){cin>>T[i];}
for(int i=1;i<=N;i++){cin>>x[i][0]>>x[i][1]>>x[i][2];if(T[1]>=x[i][0] && T[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(T[i]>=x[j][0] && T[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;}

C++: 
#include<iostream>

using namespace std;

int d,n;
int tenki[202];
int saiko[101],saitei[101];
int hade[101];
int dp[201][101];

int main(){
	cin>>d>>n;
	for(int i=0;i<d;i++){
		cin>>tenki[i];
	}
	for(int i=0;i<n;i++){
		cin>>saitei[i]>>saiko[i]>>hade[i];
	}
	for(int i=0;i<d;i++){
		for(int j=0;j<n;j++){
			if(i==0){
				dp[i][j]=0;
			}else{
				if(saitei[j]<=tenki[i]&&tenki[i]<=saiko[j]){
					int A=0;
					for(int k=0;k<n;k++){
						if(saitei[k]<=tenki[i-1]&&tenki[i-1]<=saiko[k]){
							A=max(A,dp[i-1][k]+abs(hade[k]-hade[j]));
						}
					}
					dp[i][j]=A;
				}
			}
		}
	}
	int ans=0;
	for(int 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(d), 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<bits/stdc++.h>
int P[250][150],T[250],x[250][3],D,N,M,i;
main(){memset(P,-999999,sizeof(P));cin>>D>>N;
for(i=1;i<=D;i++){std::cin>>T[i];}
for(i=1;i<=N;i++){std::cin>>x[i][0]>>x[i][1]>>x[i][2];if(T[1]>=x[i][0] && T[1]<=x[i][1]){P[1][x[i][2]]=0;}}
for(i=2;i<=D;i++){for(int j=1;j<=N;j++){if(T[i]>=x[j][0] && T[i]<=x[j][1]){
for(k=0;k<=100;k++){P[i][x[j][2]]=max(P[i][x[j][2]],P[i-1][k]+abs(x[j][2]-k));}}}}
for(i=0;i<=100;i++){M=max(M,P[D][i]);}std::cout<<M<<"\n";}

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

int d, n;
int t[202];
int a[202], b[202], c[202];

int dp[256][256][20020];

int dfs(int i=0, int front=0, int cost=0)
{
  int &ret = dp[i][front][cost];
  if (ret != -1) return ret;
  if (i == d) return cost;

  for (int j = 0; j < n; j++){
    if (t[i] < a[j] || b[j] < t[i]) continue;
    ret = max(dfs(i + 1, j, (i ? cost + abs(c[front] - c[j]) : 0)), ret);
  }

  return ret;
}

int main()
{
  memset(dp, -1, sizeof(dp));
  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];
  }

  cout << dfs() << endl;
}

C++: #include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int s[200],r[200][200];
int main(void)
{
	int n,i,j,m,t[200],a[200],b[200],c[200],k[200],h,l,z,x;
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++) scanf("%d",&t[i]);
	for(i=0;i<m;i++) scanf("%d %d %d",&a[i],&b[i],&c[i]);
	for(i=0;i<n;i++){
		k[i]=0;
		for(j=0;j<m;j++){
			if(a[j]<=t[i]&&b[j]>=t[i]){
				r[i][k[i]]=c[j];
				k[i]++;
			}
		}
	}
	for(i=0;i<200;i++) s[i]=0;
	x=0;
	for(i=0;i<n-1;i++){
		for(j=x;j<k[i];j++){
			for(l=0;l<k[i+1];l++){
//				printf("%d  %d-%d=%d\n",j,r[i][j],r[i+1][l],abs(r[i][j]-r[i+1][l]));
				if(i==0&&s[i+1]<abs(r[i][j]-r[i+1][l])){
					s[i+1]=abs(r[i][j]-r[i+1][l]);
					z=l;
				}
				else if(s[i+1]<abs(r[i][j]-r[i+1][l])){
					s[i+1]=abs(r[i][j]-r[i+1][l]);
					z=l;
				}
			}
		}
		x=z;
		k[i+1]=z+1;
	}
	h=0;
	for(i=0;i<n;i++) h+=s[i];
	printf("%d\n",h);
	return 0;
}

C++: #include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int a[300],b[300],c[300],dp[300][300],s[300],n,d,ans;
int main(){
	cin>>d>>n;
	r(i,d)cin>>s[i];
	r(i,n)cin>>a[i]>>b[i]>>c[i];
	r(i,n)if(a[i]<=s[0]&&s[0]<=b[i])dp[0][i]=1;
	for(int i=1;i<d;i++)r(j,n)r(k,n)if(dp[i-1][j])if(a[k]<=s[i]&&s[i]<=b[k])
		dp[i][k]=max(dp[i][k],dp[i-1][j]+abs(c[j]-c[k]));
	r(i,n)ans=max(ans,dp[d-1][i]);
	cout<<ans-1<<endl;
}