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 <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[2]&&temp[2]<=c2[i]){
			for(int j=0; j<N; ++j){
				if(c1[j]<=temp[1]&&temp[1]<=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]){
						for(int l=0; l<N; ++l){
							if(c1[l]<=temp[i-2]&&temp[i-2]<=c2[l]){
								dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][l]+calc(c3[j]-c3[k]));
							}
						}
					}
				}
			}
		}
	}
	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;
}

C++: #include<stdio.h>

int D,N;
int zettai;
int ans=0;

void search(int days,int list[][N],int goukei,int mae){
	if(days==D){
		if(ans<goukei){
			ans=goukei;
		}
		return;
	}
	int i;
	for(i=0;i<N;i++){
		if(list[days][i]!=-1){
			zettai=mae-list[days][i];
			if(zettai<0){
				zettai=zettai*(-1);
			}
			search(days+1,list,goukei+zettai,list[days][i]);
		}
	}
	return;
}
	
	
int main(){
	int i,j;
	scanf("%d %d",&D,&N);
	int temp[D];
	for(i=0;i<D;i++){
		scanf("%d",&temp[i]);
	}
	int list[D][N];
	int min[N],max[N],hade[N];
	for(i=0;i<N;i++){
		scanf("%d %d %d",&min[i],&max[i],&hade[i]);
		for(j=0;j<D;j++){
			list[j][i]=-1;
		}
	}
	for(i=0;i<D;i++){
		for(j=0;j<N;j++){
			if(min[j]<=temp[i]&&temp[i]<=max[j]){
				list[i][j]=hade[j];
			}
		}
	}
	for(i=0;i<N;i++){
		if(list[0][i]!=-1){
			search(1,list,0,list[0][i]);
		}
	}
	printf("%d",ans);
	return 0;
}

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];

int solve(int d, int k, int e){
	cout << d << " " << k << " " << e << "   " << score[d][k] << endl;
	//score[d][k] = e;
	if(score[d][k] > e) return 0;
	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, 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<iostream>
#include<algorithm>

using namespace std;

int a[200], b[200], c[200], d, n, t[200], dp[200][200];//dp[i][j] i??\?????????j???????????¨???????????§

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];
	}

	for (int i = 0; i < d;i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (a[j] <= t[i] && b[j] >= t[i])
			{
				if (i == 0)
				{
					dp[i][j] = 0;
				}
				else
				{
					for (int k = 0; k < n; k++)
					{
						if (dp[i - 1][k] != -1)
						{
							dp[i][j] = max(dp[i][j], dp[i - 1][k] + abs(c[j] - c[k]));
						}
					}
				}
			}
			else
			{
				dp[i][j] = -1;
			}
		}
	}

	sort(dp[d-1], dp[d-1] + n);

	cout << dp[d - 1][n - 1] << endl;

	return 0;
}

C++: #include<iostream>
#include<cassert>
#include<algorithm>
#include<vector>
#include<map>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define INF 10000000
#define S second
#define F first
using namespace std;

typedef pair<int,int> P;
typedef pair<P,int> Pi;

int main()
{
  int D,N;
  cin >> D >> N;
  vector<int> T;
  rep(i,D)
    {
      int input;
      cin >> input;
      T.push_back(input);
    }

  vector<Pi> ABC;
  rep(i,N)
    {
      int A,B,C;
      cin >> A >> B >> C;
      ABC.push_back(Pi(P(A,B),C));
    }

  P lim[D+1];
  rep(i,D+1)
    {
      lim[i] = P(INF,-1);
    }

  for(int i=0;i<D;i++)
    {
      for(int j=0;j<N;j++)
	{
	  if(ABC[j].first.first <= T[i] && T[i] <= ABC[j].first.second)
	    {

	      lim[i].first = min(lim[i].first,ABC[j].second);

	      lim[i].second = max(lim[i].second,ABC[j].second);
	      
	      if(lim[i].first == INF && lim[i].S != -1)
		lim[i].F = lim[i].S;
	     
	      if(lim[i].S == -1 && lim[i].F != INF)
		lim[i].S = lim[i].F;
	      
	    }
	}
    }

  /*
  for(int i=0;i<D;i++)
    {
      cout << i << " - th" << endl;
      cout << "min : " << lim[i].F << " max : "<< lim[i].S << endl;
    }
  */

  long long int ans = 0;
  for(int i=0;i<D-1;i++)
    {
      int mex,men,pre;
      pre = -1;
      if(lim[i].first != INF && lim[i+1].second != -1)
	{
	  pre = max(pre,abs(lim[i].first-lim[i+1].second));
	}
      if(lim[i].second != -1 && lim[i+1].first != INF)
	{
	  pre = max(pre,abs(lim[i+1].first-lim[i].second));
	}
      if(pre == -1)
	assert(false);

      ans += pre;
    }
  cout << ans << endl;



  return 0;
}

C++: #include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>

using namespace std;

struct cloth{
	cloth(int a, int b, int c):maxtem(a), mintem(b), gaudy(c){}
	int maxtem;
	int mintem;
	int gaudy;
};

struct state{
	state(bool a, int b):mark(a), count(b){}
	bool mark;
	int count;
};

int main(){
	int d, n;
	cin >> d >> n;
	vector<int> maxtem(d, 0);
	for(int i = 0; i < d; i++){
		cin >> maxtem[i];
	}
	vector<cloth> c(n, cloth(0, 100, 0));
	for(int i = 0; i < n; i++){
		cin >> c[i].mintem >> c[i].maxtem >> c[i].gaudy;
	}

	vector<vector<state> > table(d, vector<state>(20001, state(false, 0)));
	for(int i = 0; i < d; i++){
		for(int j = 0; j < n; j++){
			if(maxtem[i]>=c[j].mintem&&maxtem[i]<=c[j].maxtem){
				if(!i){
					table[i][c[j].gaudy].mark = true;
					continue;
				}
				int max = 0;
				int index = 0;
				for(int k = 0; k < table[i-1].size(); k++){
					if(table[i-1][k].mark){
						int tmp = c[j].gaudy-k;
						if(tmp<0) tmp *= -1;
						if(max<=tmp){
							max = tmp;
							index = k;
						}
					}
				} 
				table[i][c[j].gaudy].mark = true;
				table[i][c[j].gaudy].count = max + table[i-1][index].count;
			}
		}
	}

	int max = 0;
	for(int i = 0; i < table[d-1].size(); i++){
		if(max<table[d-1][i].count) max = table[d-1][i].count; 
	}
	cout << max << endl;
	return 0;
}