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<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

int n, m;
int day[200], a[200], b[200], c[200];
int dp[200][200];//dp[i][j] i - 1テヲツ猟・テァツ崢ョテ」ツ?ォテヲツ慊綱 - 1テ」ツつ津ァツ敖?」ツ?淌ヲツ卍づ」ツ?ョテ」ツδ凖」ツつケテ」ツδ暗」ツ?ョテ・ツ?、

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)cin >> day[i];
	for (int i = 0; i < m; i++)cin >> a[i] >> b[i] >> c[i];
	for (int i = 1; i < n; i++) {
		int tmp = 0;
		for (int j = 0; j < m; j++) {
			int ans = 0;
			if (a[j] <= day[i] && day[i] <= b[j]) {
				for (int k = 0; k < m; k++) {
					if (a[k] <= day[i - 1] && day[i - 1] <= b[k]) {
						ans = max(ans, dp[i - 1][k] + abs(c[j] - c[k]));
					}
				}
			}
			dp[i][j] = ans;
		}
	}
	int ans = 0;
	for (int i = 0; i < m; i++)ans = max(ans, dp[n - 1][i]);
	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;
}

C++: #include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct ABC{
int a,b,c;
};
int main(){
int i,j,l,n,d,t[200],p[201][200]={0};
struct ABC q[200];
scanf("%d%d",&d,&n);
for(i=0;i<d;i++)
scanf("%d",&t[i]);
for(i=0;i<n;i++)
scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].c);
for(i=1;i<d;i++){
	for(j=0;j<n;j++){
		if(t[i-1]>=q[j].a&&t[i-1]<=q[j].b){
			for(l=0;l<n;l++){
				if(t[i]>=q[l].a&&t[i]<=q[l].b){
					int absl=max(q[j].c-q[l].c,q[l].c-q[j].c);
					p[i][l]=max(p[i][l],p[i-1][j]+absl);
				}
			}
		}
	}
}
int ans=0;
for(i=0;i<n;i++)
ans=max(ans,p[d-1][i]);
printf("%d\n",ans);
return 0;
}

C++: #include <cstdio>
#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 solve() {
    int dp[MD+1][MN+1];
    for (int i = 0; i < D; i++) {
        for (int j = 0; j < N; j++) {
            if (CA[j] <= T[i] && T[i] <= CB[j]) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = -1;
            }
        }
    }
    for (int i = 1; i < D; i++) {
        for (int j = 0; j < N; j++) {
            if (dp[i][j] < 0) continue;
            for (int k = 0; k < N; k++) {
                if (dp[i-1][k] < 0) continue;
                dp[i][j] = max(dp[i][j], dp[i-1][k] + abs(CC[j] - CC[k]));
            }
        }
    }
    int ret = 0;
    for (int i = 0; i < D; i++) {
        for (int j = 0; j < N; j++) {
            ret = max(ret, dp[i][j]);
        }
    }
    //for (int i = 0; i < D; i++) {
    //    for (int j = 0; j < N; j++) {
    //        printf("%4d", dp[i][j]);
    //    }
    //    printf("\n");
    //}
    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<stdio.h>
#include<cstdio>
#include<algorithm>
#include<functional>
#include<ctype.h>
using namespace std;
int temp;
int d,n;
int t[10000];
int a[10000],b[10000],c[10000];
int dp[10000][10000];
int i,j,k;
int main(void){
	int max=0;
	scanf("%d %d",&d,&n);	//d=見る日数 n=服の種類
	for(i=0;i<d;i++){
		scanf("%d",&t[i]);	//i日目の最高温度
	}
	for(i=0;i<d;i++){
		for(j=0;j<n;j++){
			dp[i][j]=-1;	//派手さ
		}
	}
	for(i=0;i<n;i++){
		scanf("%d %d %d",&a[i],&b[i],&c[i]);	//a=最低温度 b=最高温度 c=派手
	}
	for(i=0;i<n;i++){
		if(a[i]<=t[0] && b[i]>=t[0]){
			dp[0][i]=0;
		}
	}
	for(i=1;i<d;i++){
		for(j=0;j<n;j++){
			if(dp[i-1][j]!=-1){
				for(k=0;k<n;k++){
					if(a[k]<=t[i] && b[k]>=t[i]){
						if(dp[i][k]==-1) {
							dp[i][k]=0;
						}
						temp=c[k]-c[j];
						//printf("c[k]%d c[j]%d\n",c[k],c[j]);
						if(temp<0)	temp=0-temp;
						if(max<=temp){
							max=temp;
						}
						//printf("max%d\n",max);
						//printf("dpa%d i=%d k=%d\n",dp[i][k],i,k);
						if(dp[i][k]<=dp[i-1][j]+max){
							dp[i][k]=dp[i-1][j]+max;
						//printf("aa%d %d %d %d\n",dp[i][j],dp[i][k],i,j);
						}
					}
			max=0;
				}
			}
			//printf("\n");
		}
		//printf("\n");
	}
	/*for(i=0;i<d;i++){ //でバグ
		printf("%d\n",t[i]);
		for(j=0;j<n;j++){
			printf("%d ",dp[i][j]);
		}
		printf("\n");
	}*/			
	max=0;
	for(j=0;j<n;j++){
		//printf("%d ",dp[d-1][j]);
		if(dp[d-1][j]>max){
			max=dp[d-1][j];
		}
	}
	//printf("\n");
	printf("%d\n",max);
	return 0;
}

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

using namespace std;

int main(void){

  int d,n,t,a,b,c,dp[202][202];
  vector<int>T,A,B,C;

  while(cin >> d >> n,d|n){
    T.clear();
    A.clear();
    B.clear();
    C.clear();

    for(int i=0;i<d;i++){
      cin >> t;
      T.push_back(t);
    }


    for(int i=0;i<n;i++){
      cin >> a >> b >> c;
      A.push_back(a);
      B.push_back(b);
      C.push_back(c);
    }

    for(int i=0;i<202;i++)
      for(int j=0;j<202;j++)
	dp[i][j]=-1;

    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
       
	  if(A[i]<=T[0] && T[0]<=B[i] && A[j]<=T[1] && T[1]<=B[j])
	    dp[0][j]=max(dp[0][j],abs(C[i]-C[j]));
	}
    }

    for(int i=1;i<=d;i++){
      for(int j=0;j<n;j++){
	for(int k=0;k<n;k++){
	    if(A[k]<=T[i] && T[i]<=B[k] && dp[i-1][j]>=0)
	      dp[i][k]=max(dp[i][k],dp[i-1][j]+abs(C[j]-C[k]));
	}
      }
    }

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

  }


  return 0;
}