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<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define int long long
static const int INF = 8931919114514810;
static const int MAX_N = 300;
using namespace std;

int A[300],B[300],C[300];
int mem[MAX_N][MAX_N];
int N,D;
int Day[MAX_N];
int cal(int day,int pp){
   int res=0;
   if(day==N+1){
        return res=0;
   }
   if(mem[day][pp]!=-1){
        return res=mem[day][pp];
   }
    FOR(i,1,D){
        if(Day[day]>=A[i]&&Day[day]<=B[i]){
            int temp=abs(pp-C[i]);
            if(day==1){
                res=cal(day+1,C[i]);
            }
            else {
                res=max(cal(day+1,C[i])+temp,res);
                mem[day][pp]=res;
            }
        }
    }
   return mem[day][pp]=res;
}

signed main(){
    cin>>N>>D;
    fill(mem[0],mem[MAX_N],-1);
    FOR(i,1,N){
        cin>>Day[i];
    }
    FOR(i,1,D){
        cin>>A[i]>>B[i]>>C[i];
    }
    cout<<cal(1,0)<<endl;
    return 0;
}

C++: #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[150],B[150],C[150];
};

int N,D;
LL res=-INF;
LL Day[150];
LL mem[110][110][110];
clothes T;

LL cal(LL day,LL p,LL pp,LL sum){
    if(res<sum+abs(pp-p))res=sum+abs(pp-p);
    //if(mem[day][p][pp]!=0)return mem[day][p][pp];
    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 mem[day][p][pp]=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];
        cout<<cal(0,0,0,0)<<endl;
}

C++: #include<stdio.h>
#include<algorithm>
using namespace std;
int dp[200][101];
int c[200];
int d[200];
int e[200];
int f[200];
int ABS(int a){return max(a,-a);}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%d",c+i);
	for(int i=0;i<b;i++)scanf("%d%d%d",d+i,e+i,f+i);
	for(int i=0;i<a;i++)
		for(int j=0;j<101;j++)
			dp[i][j]=-99999999;
	for(int i=0;i<b;i++)if(d[i]<=c[0]&&c[0]<=e[i])dp[0][f[i]]=0;
	for(int i=0;i<a-1;i++){
		for(int j=0;j<101;j++){
			if(dp[i][j]>=0){
				for(int k=0;k<b;k++)if(d[k]<=c[i+1]&&c[i+1]<=e[k])dp[i+1][f[k]]=max(dp[i+1][f[k]],dp[i][j]+ABS(j-f[k]));
			}
		}
	}
	int ret=0;
	for(int i=0;i<101;i++)ret=max(ret,dp[a-1][i]);printf("%d\n",ret);
}

C++: #include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<stack>
#include<vector>
#include<set>
#include<queue>

using namespace std;

int main()
{
	int A[200],B[200],C[200],D,N,T[200];
	int sum1,sum2 = 0;
	vector<int>select[200];//vector[??\][????????°] =????´???????
	cin >> D >> N;
	for(int a = 0;a<D;a++)
	{
		cin >> T[a];
	}
	for(int a = 0;a<N;a++)
	{
		cin >> A[a] >> B[a] >> C[a];

	}

	int b;

	for(int a = 0;a<D;a++)
	{
		for(b = 0;b<N;b++)
		{
			if(A[b]<=T[a]&&T[a]<=B[b])
			{
				select[a].push_back(C[b]);
			}
		}
	}

	sort(select[0].begin(),select[0].end());

	int c = 0;

	for(int a = 0;a<D-1;a++)
	{
		if(c == 0)
		{
			sort(select[a+1].begin(),select[a+1].end(),greater<int>());
			if(*select[a].begin() > *select[a+1].begin())
			{
				sum1 += *select[a].begin() - *select[a+1].begin();
			}
			else
			{
				sum1 += *select[a+1].begin() - *select[a].begin();
			}
			c++;
		}
		else
		{
			sort(select[a+1].begin(),select[a+1].end());
			if(*select[a].begin() > *select[a+1].begin())
			{
				sum1 += *select[a].begin() - *select[a+1].begin();
			}
			else
			{
				sum1 += *select[a+1].begin() - *select[a].begin();
			}
			c--;
		}
	}

	sort(select[0].begin(),select[0].end(),greater<int>());

	for(int a = 0;a<D-1;a++)
	{
		if(c == 0)
		{
			sort(select[a+1].begin(),select[a+1].end());
			if(*select[a].begin() > *select[a+1].begin())
			{
				sum2 += *select[a].begin() - *select[a+1].begin();
			}
			else
			{
				sum2 += *select[a+1].begin() - *select[a].begin();
			}
			c++;
		}
		else
		{
			sort(select[a+1].begin(),select[a+1].end(),greater<int>());
			if(*select[a].begin() > *select[a+1].begin())
			{
				sum2 += *select[a].begin() - *select[a+1].begin();
			}
			else
			{
				sum2 += *select[a+1].begin() - *select[a].begin();
			}
			c--;
		}
	}

	cout << max(sum1,sum2) << endl;

	return 0;
}

C++: #include<stdio.h>
long long int dp[1001][1001];
int main(void)
{
	int D,N,x=0,i,j,k,r=0;
	int T[1001],A[1001],B[1001],C[1001];
	scanf("%d%d",&D,&N);
	for(i=1;i<=D;i++){
		scanf("%d",&T[i]);
	}
	for(i=1;i<=N;i++){
		scanf("%d%d%d",&A[i],&B[i],&C[i]);
	}
	for(i=1;i<=D;i++){
		for(j=1;j<=N;j++){
			dp[i][j]=-1;
		}
	}
	for(i=1;i<=D;i++){
		for(j=1;j<=N;j++){
			if(A[j]<=T[1]&&T[1]<=B[j]){
				dp[1][j]=0;
			}
			if(A[j]<=T[i]&&T[i]<=B[j]){
				for(k=1;k<=N;k++){
					if(A[k]<=T[i+1]&&T[i+1]<=B[k]){
						r=C[j]-C[k];
						if(r<0){
							r*=-1;
						}
						if(dp[i+1][k]<dp[i][j]+r){
							dp[i+1][k]=dp[i][j]+r;
						}
					}
				}
			}
		}
	}
	/*for(i=D;i>0;i--){
		for(j=1;j<=N;j++){
			printf("%d ",dp[i][j]);
		}
		printf("\n");
	}*/
	for(i=0;i<N;i++){
		if(x<dp[D][i]){
			x=dp[D][i];
		}
	}
	printf("%d\n",x);
	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;
}