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 <algorithm>
#include <cstdlib>
using namespace std;

int d, n;
int t[200];
int c[200][3];
int dp[200][200];
const int INF = 100100100;

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++)
		for(int j=0; j<3; j++)
			scanf("%d", &c[i][j]);

	for(int i=0; i<n; i++){
		if(c[i][0] <= t[0] && t[0] <= c[i][1]){
		}else{
			dp[0][i] = -INF;
		}
	}
	for(int i=1; i<d; i++){
		for(int j=0; j<n; j++){
			if(c[j][0] <= t[i] && t[i] <= c[j][1]){
				for(int k=0; k<n; k++){
					dp[i][j] = max(dp[i][j], dp[i-1][k] + abs(c[j][2] - c[k][2]));
				}
			}
		}
	}
/*
	for(int i=0; i<d; i++){
		for(int j=0; j<n; j++)
			printf("%d\t", dp[i][j]);
		printf("\n");
	}
*/
	int ans = 0;
	for(int i=0; i<n; i++)
		ans = max(ans, dp[d-1][i]);
	printf("%d\n", ans);
	return 0;
}

C++: #include<cstdio>
#include<algorithm>
#include<functional>
#include<cstring>
#include<iostream>
#include<cmath>
#include<queue>
#include<cctype>
#include<string>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define INF 2100000000
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define lb lower_bound
#define ub upper_bound
#define SS stringstream
#define sz(x) ((int)(x).size())
#define SORT(x) sort((x).begin(), (x).end())
#define RSORT(x) sort((x).begin(), (x).end(), greater<int>() )
#define clr(a,b) memset((a),(b),sizeof(a))
int dp[4545][4545],mxc[4545],a[4545],b[4545],c[4545];
int main(void)
{
	int d,n,sa,mx;
	cin>>d>>n;
	rep(i,0,d) cin>>mxc[i];
	rep(i,0,n) cin>>a[i]>>b[i]>>c[i];
	rep(i,0,d)rep(j,0,n) dp[i][j]=0;
	rep(i,0,d) {
		rep(j,0,n) {
			if(a[j]<=mxc[i]&&mxc[i]<=b[j]) {
				rep(k,0,n) {
					if(a[k]<=mxc[i+1]&&mxc[i+1]<=b[k]) {
						sa=abs(c[j]-c[k]);
						dp[i+1][k]=max(dp[i][j]+sa,dp[i+1][k]);
					}
				}
			}
		}
	}
	rep(i,0,n) mx=max(mx,dp[d-1][i]);
	cout<<mx<<endl;
	return 0;
}

C++: #include<iostream>
using namespace std;
int day, n, ans;
int d[201], dp[201][201];
int clo[201][3];
int main(){
  cin>>day>>n;
  for(int i=1;i<=day;i++)
    cin>>d[i];
  for(int i=1;i<=n;i++){
    cin>>clo[i][0]>>clo[i][1]>>clo[i][2];
  }
  for(int i=1;i<=day;i++){
    for(int j=1;j<=n;j++){
      if(clo[j][0]>d[i]&&clo[j][1]<d[i]){
	for(int k=1;k<=n;k++){
	  dp[i][j]=max(dp[i][j],abs(clo[k][2]-clo[j][2])+dp[i-1][k]);
	}
      }
    }
  }
  for(int i=1;i<=n;i++)
    ans=max(ans,dp[day][i]);
  cout<<ans<<endl;
}

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

#define llong long long 
typedef struct data{
	int low;
	int high;
	int eva;
}data;
int D, N;
int temp[201];
data kind[200];
int score[201][200][200];

int solve(int d, int k, int e){
	if(d == D) return e;
	int ret = 0;
	for(int i = 0; i < N; i++){
		data use = kind[i];
		if(use.low > temp[d + 1] || use.high < temp[d + 1]) continue;
		if(d > 0) ret = max(ret, solve(d + 1, i, e + fabs(kind[k].eva - kind[i].eva)) );
		else ret = max(ret, solve(d + 1, i, 0));
	}

	return ret;
}

int main(){
	fill_n(temp, 201, -1);
	fill_n(**score, 201 * 200 * 200, 0);
	cin >> D >> N;
	for(int i = 1; i <= D; i++){
		cin >> temp[i];
	}
	for(int i = 0; i < N; i++){
		cin >> kind[i].low >> kind[i].high >> kind[i].eva;
	}

	cout << solve(0, 0, -1) << endl;
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int main(){
  int n,d,t[200],a[200],b[200],c[200];
  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 dp[201][101];
  for(int i=0;i<201;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]==-1)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]));
	  // cout<<i<<" "<<j<<endl;
	}
    }
  }
  int ans=0;
  for(int i=0;i<101;i++)ans=max(ans,dp[d-1][i]);
  cout<<ans<<endl;
  return 0;
}

C++: #include<stdio.h>
#include<stdlib.h>
#include<algorithm>

struct str
{
	int a, b, c;
};
int t[200];
str b[200];
str dp1[200];
str dp2[200];
int main(){
	int d, n;
	scanf("%d%d", &d, &n);
	for (int i = 0; i < d; i++)
		scanf("%d", &t[i]);
	for (int i = 0; i < n; i++){
		int a_, b_, c_;
		scanf("%d%d%d", &a_, &b_, &c_);
		b[i].a = a_;
		b[i].b = b_;
		b[i].c = c_;
	}
	int min = 101;
	for (int i = 0; i < n; i++)
		if (b[i].a <= t[0] && t[0] <= b[i].b&&min >=b[i].c)
			min = b[i].c;
	dp1[0].a = 0; dp1[0].b = min;
	for (int i = 1; i < d; i++){
		int max = 0;
		for (int j = 0; j < n; j++){
			if (b[j].a <= t[i] && t[i] <= b[j].b&&abs(dp1[i - 1].b - b[j].c) >= max){
				max = abs(dp1[i - 1].b - b[j].c);
				dp1[i].b = b[j].c;
			}
		}
		dp1[i].a = dp1[i - 1].a + max;
	}
	int max = 0;
	for (int i = 0; i < n; i++)
		if (b[i].a <= t[0] && t[0] <= b[i].b&&min <= b[i].c)
			max = b[i].c;
	dp2[0].a = 0; dp2[0].b = min;
	for (int i = 1; i < d; i++){
		max = 0;
		for (int j = 0; j < n; j++){
			if (b[j].a <= t[i] && t[i] <= b[j].b&&abs(dp2[i - 1].b - b[j].c) >= max){
				max = abs(dp2[i - 1].b - b[j].c);
				dp2[i].b = b[j].c;
			}
		}
		dp2[i].a = dp2[i - 1].a + max;
	}
	printf("%d\n",std::max(dp1[d - 1], dp2[d - 1]));
	return 0;
}

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][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){
			for(int k=0; k<201; ++k){
				dp[i][j][k]=0;
			}
		}
	}
	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);
	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 i=0; i<N; ++i){
		if(c1[i]<=temp[1]&&temp[1]<=c2[i]){
			for(int j=0; j<N; ++j){
				if(c1[j]<=temp[2]&&temp[2]<=c2[j]){
					dp[2][i][j]=calc(c3[i]-c3[j]);
				}
			}
		}
	}
	for(int i=3; i<=D; ++i){
		for(int j=0; j<N; ++j){
			if(c1[j]<=temp[i]&&temp[i]<=c2[j]){
				for(int k=0; k<N; ++k){
					if(c1[k]<=temp[i-1]&&temp[i-1]<=c2[k]){
						int hoge=0;
						for(int l=0; l<N; ++l){
							hoge=max(hoge,dp[i-1][k][l]+calc(c3[j]-c3[k]));
						}
						dp[i][j][k]+=hoge;
					}
				}
			}
		}
	}
	for(int i=0; i<N; ++i){
		for(int j=0; j<N; ++j){
			ans=max(ans,dp[D][i][j]);
		}
	}
	cout << ans << "\n";
	return 0;
}