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<algorithm>
using namespace std;
int abs(int a){if(a<0)a*=-1;return a;}
int main(){
   int D,N,T[300],A[300],B[300],C[300],dp[300][300];
   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];
   fill(dp[0],dp[0]+90000,-1);

   for(int i=0;i<N;i++){
        if(A[i]<=T[0]&&B[i]>=T[0])dp[0][i]=0;
   }

   for(int i=0;i<D-1;i++){
        for(int j=0;j<N;j++){
            if(dp[i][j]==-1)continue;
            for(int k=0;k<N;k++){
                if(A[k]>T[i+1]||B[k]<T[i+1])continue;
                dp[i+1][k]=max(dp[i+1][k],dp[i][j]+abs(C[j]-C[k]));
            }
        }
   }
   int M=-1;
   for(int i=0;i<N;i++)M=max(M,dp[D-1][i]);
   cout<<M<<endl;
  
}

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

using namespace std;

int t[200];

int a[200];
int b[200];
int c[200];

int dp[2][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++)
	{
		scanf("%d%d%d",a + i,b + i,c + i);
	}
	int now = 0;
	for(int i = 0; i < n; i++)
	{
		if(a[i] <= t[0] && t[0] <= b[i])
		{
			dp[now][i] = 0;
		}
		else
		{
			dp[now][i] = -1000000;
		}
	}
	for(int i = 1; i < d; i++)
	{
		int nex = (now + 1) % 2;
		for(int j = 0; j < n; j++)
		{
			dp[nex][j] = -1000000;
		}
		for(int j = 0; j < n; j++)
		{
			if(a[j] <= t[i] && t[i] <= b[j])
			{
				for(int jj = 0; jj < n; jj++)
				{
					dp[nex][j] = max(dp[nex][j],dp[now][jj] + abs(c[j] - c[jj]));
				}
			}
		}
		now = nex;
	}
	int maxw = -1000000;
	for(int i = 0; i < n; i++)
	{
		maxw = max(maxw,dp[now][i]);
	}
	printf("%d\n",maxw);
	return 0;
}

C++: #include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
#define INF (1 << 29)
using namespace std;

struct Clothes{
    int low, up, glitz;
};

int dp[205][205];
int d, n, t[205];
Clothes c[205];

void update(int day, int before, int now){
    if(c[now].low <= t[day] && c[now].up >= t[day]){
        if(day == 0) dp[day][now] = 0; //テ・ツ按敕ヲツ猟・テ」ツ?ォテァツ敖?」ツつ凝ヲツ慊?
        else if(dp[day - 1][before] != INF){
            dp[day][now] = max(dp[day][now], dp[day - 1][before] + abs(c[before].glitz - c[now].glitz)); 
        }
    }
}

int solve(){
    rep(day,d){
        rep(before,n){
            rep(now,n){
                update(day, before, now);
            }
        }
    }

/*
    rep(i,d){
        rep(j,n){
            cout << dp[i][j] << ' ';
        }
        cout << endl;
    }
*/

    int retval = -1;
    rep(i,n){
        if(dp[d - 1][i] >= INF) continue;
        retval = max(retval, dp[d - 1][i]);
    }
    return retval;
}

int main(){
    rep(i,105) rep(j,105) dp[i][j] = -1 * INF;
    cin >> d >> n;
    rep(i,d) cin >> t[i];
    rep(i,n) cin >> c[i].low >> c[i].up >> c[i].glitz;
    cout << solve() << endl;
}

C++: #include<iostream>
#include<vector>
using namespace std;
#define inRange(x,a,b) (a <= x && x <= b)

int main(){
    int d, n;
    cin >> d >> n;
    vector<int> t(d);
    for(int i = 0; i < d; i++)  cin >> t[i];
    vector<int> a(n), b(n), c(n);
    for(int i = 0; i < n; i++)  cin >> a[i] >> b[i] >> c[i];
    vector<vector<int>> dp(d, vector<int>(n, 0));
    for(int i = 0; i < d-1; i++){
        for(int j = 0; j < n; j++){
            if(!inRange(t[i], a[j], b[j]))  continue;
            for(int k = 0; k < n; k++){
                if(!inRange(t[i+1],a[k],b[k]))  continue;
                dp[i+1][k] = max(dp[i+1][k], dp[i][j] + abs(c[j]-c[k]));
            }
        }
    }
    int ans = 0;
    for(int k = 0; k < n; k++)  ans = max(ans, dp[d-1][k]);
    cout << ans << endl;
    return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<cmath>
#define INF 1<<28
using namespace std;

int a[222], b[222], c[222];
int d, n;
int t[66];
int memo[66][222];

int solve(int p, int q){
  if(p == d-1) return 0;
  if(memo[p][q]) return memo[p][q];
  
  int ret = -INF;
  for(int i=0;i<n;i++) 
    if(a[i] <= t[p+1] && t[p+1] <= b[i])
      ret = max(solve(p+1, i)+abs(c[q]-c[i]), ret);
  
  return memo[p][q] = ret;
}

int main(){
  
  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 = -(1<<28);
  for(int i=0;i<n;i++)
    if(a[i] <= t[0] && t[0] <= b[i])
      ans = max(solve(0, i), ans);
  
  cout << ans << endl;
}

C++: //AOJ 0579: Hot days
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, int> P;
const int INF = 10000000;
int n, d, ans, c[200][61], save[3], dt[200], plan[101][2], s[200][101];
void solve(){
	for (int i = 1; i < d; i++){
		if (plan[i][0] == plan[i][1]){
			s[i][plan[i][0]] = max(s[i - 1][plan[i - 1][0]] + abs(plan[i][0] - plan[i - 1][0]), s[i - 1][plan[i - 1][1]] + abs(plan[i][0] - plan[i - 1][1]));
		}

		else{
			s[i][plan[i][0]] = max(s[i - 1][plan[i - 1][0]] + abs(plan[i][0] - plan[i - 1][0]), s[i - 1][plan[i - 1][1]] + abs(plan[i][0] - plan[i - 1][1]));
			s[i][plan[i][1]] = max(s[i - 1][plan[i - 1][0]] + abs(plan[i][1] - plan[i - 1][0]), s[i - 1][plan[i - 1][1]] + abs(plan[i][1] - plan[i - 1][1]));
		}
	}
	ans = max(s[d - 1][plan[d - 1][0]], s[d - 1][plan[d - 1][1]]);
}
int main(){
	cin >> d >> n;
	for (int i = 0; i < d; i++){
		cin >> dt[i];
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j<61; j++){
			c[i][j] = -1;
		}
	}
	for (int i = 0; i < n; i++){
		cin >> save[0] >> save[1] >> save[2];
		for (int j = save[0]; j <= save[1]; j++){
			c[i][j] = save[2];
		}
	}
	for (int i = 0; i<d; i++){
		plan[i][0] = INF;
	}
	for (int i = 0; i < d; i++){
		for (int j = 0; j < n; j++){
			if (c[j][dt[i]] != -1){
				plan[i][0] = min(c[j][dt[i]], plan[i][0]);
				plan[i][1] = max(c[j][dt[i]], plan[i][1]);
			}
		}
	}
	solve();
	cout << ans << endl;
	return 0;
}

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

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define MP make_pair

typedef pair<int, int> PII;

int d, n, mt[200];
PII clothes[200];
vector<PII> v;
int result[200];

int search(int tem, int di) {
  int ni, res = 0;
  if (di == 1) ni = 0;
  else ni = n - 1;

  while (0 <= ni && ni < n) {
    PII nc = clothes[v[ni].second];
    if (nc.first <= tem && nc.second >= tem) return res = v[ni].first;
    ni += di;
  }

  return 0;
}

int culc() {
  int res = 0;
  REP(i, d - 1) res += abs(result[i] - result[i+1]);
  return res;
}

int main() {
  cin >> d >> n;
  REP(i, d) scanf("%d", &mt[i]);
  v.resize(n);
  REP(i, n) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    clothes[i] = MP(a, b);
    v[i] = MP(c, i);
  }
  sort(v.begin(), v.end());

  int ans = -1;
  int di[] = {1, -1};
  REP(i, 2) {
    REP(j, d) result[j] = search(mt[j], di[(j+i)%2]);
    ans = max(ans, culc());
  }

  cout << ans << endl;
  return 0;
}