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

using namespace std;

struct Tshirt{
	int a;
	int b;
	int c;
};

int solve(int,struct Tshirt);

int d,n;
int t[201];
int memo[210][210];
struct Tshirt data[201];

int main(){
	cin >> d >> n;
	for(int i=1;i<=d;i++){
		cin >> t[i];
	}
	for(int i=1;i<=n;i++){
		cin >> data[i].a;
		cin >> data[i].b;
		cin >> data[i].c;
	}
	int ans = 0;
	for(int i=1;i<=n;i++){
		if(t[1] >= data[i].a && t[1] <= data[i].b){
			int new_ans=0;
			new_ans = solve(2,data[i],i);
			if(ans < new_ans)ans = new_ans;
		}
	}

	cout << ans  << endl;
	return 0;
}
int solve(int day,struct Tshirt a){
	int rec = 0;
	if(memo[day][a.c] != 0)return memo[day][a.c];
	if(day == d){
		rec = 0;
	}
	for(int i=1;i<=n;i++){
		int o;
		if(t[day] >= data[i].a && t[day] <= data[i].b){
			o = abs(a.c-data[i].c);
			o += solve(day+1,data[i],i);
			rec = max(rec,o);
		}
	}	
	memo[day][a.c] = rec;
	return rec;
}

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

const int INF = 33554432;

struct W
{
        int min, max;
        int c;
};

std::vector< W > ws;
std::vector< int > ts;
int n;
int m;

long solve( int d, W before )
{
        if ( d == n )
        {
                return 0;
        }

        long res = -INF;
        for ( int i = 0; i < m; ++i )
        {
                if ( ws[ i ].min <= ts[ d ] && ts[ d ] <= ws[ i ].max )
                {
                        if ( d == 0 )
                        {
                                res = std::max( res, solve( d + 1, ws[ i ] ) );
                        }
                        else {
                                res = std::max( res, solve( d + 1, ws[ i ] ) + std::abs( before.c - ws[ i ].c ) );
                        }
                }
        }

        return res;
}

int main()
{
        std::cin >> n >> m;
        ts.resize( n );
        ws.resize( m );
        for ( int i = 0; i < n; ++i )
        {
                std::cin >> ts[ i ];
        }
        for ( int i = 0; i < m; ++i )
        {
                std::cin >> ws[ i ].min >> ws[ i ].max >> ws[ i ].c;
        }

        W dummy;
        std::cout << solve( 0, dummy ) << std::endl;
        
}

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

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

LL cal(LL day,LL p,LL pp,LL sum){
    //cout<<sum+abs(pp-p)<<" "<<day<<" "<<p<<" "<<pp<<endl;
    if(mem[day][p][pp]!=0){
        res=mem[day][p][pp];
        mem[day][p][pp]=0;
    }
    else{
        if(res<sum+abs(pp-p)&&day==N+1)mem[day][p][pp]=res=sum+abs(pp-p);
        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 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 <bits/stdc++.h>
using namespace std;

struct uyu{int a, b, c;};

int d, n;
int t[202];
vector<uyu> po;

int dfs(int i, int cost, int front)
{
  int ret = 0;
  
  if (i == d) return cost;
  if (i == 0){
    for (auto &j : po){
      if (t[i] < j.a || j.b < t[i]) continue;
      ret = max(ret, dfs(i + 1, 0, j.c));
    }
    return ret;
  }

  for (auto &j :po){
    if (t[i] < j.a || j.b < t[i]) continue;
    ret = max(ret, dfs(i + 1, cost + abs(front - j.c), j.c));
  }

  return ret;
}

int main()
{
  cin >> d >> n;
  for (int i = 0; i < d; i++){
    cin >> t[i];
  }

  for (int i = 0; i < n; i++){
    uyu s;
    cin >> s.a >> s.b >> s.c;
    po.push_back(s);
  }

  cout << dfs(0, 0, 0) << endl;
}

C++: #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
#include <sstream>
#include <string>
#include <map>
using namespace std;
#define FOR(I,N) for(int I = 0; I < (int)(N); I++)
#define fin(V) cout<< V <<endl
#define INF 114514
string sValueOf(int v){stringstream ss;ss<<v;return ss.str();}
int parseInt(string v){int i;stringstream ss(v);ss>>i;return i;}

int D, N;
int day[201];
int MIN[201], MAX[201], rare[201];
int dp[201][201];
int mx = 0;
int solve(int day, int now, int bef);


int solve(int n, int b){
	if(n == D)
		return 0;
	if(dp[n][b] != -1){
		return dp[n][b];
	}

	int mx = 0;
	for(int i = 0; i < N; i++){
		if(MAX[i] >= day[n] && MIN[i] <= day[n]){
			mx = max(mx, abs(rare[i] - b) + solve(n+1, rare[i]));
		}
	}
	return dp[n][b] = mx;
}


int main(){
	fill_n(*dp, 201*201, -1);
	cin >> D >> N;
	for(int i = 0; i < D; i++){
		cin >> day[i];
	}
	for(int i = 0; i < N; i++){
		cin >> MIN[i] >> MAX[i] >> rare[i];
	}

	int mx = 0;
	//一番最初の服を決める
	for(int i = 0; i < N; i++){
		if(MAX[i] >= day[0] && MIN[i] <= day[0]){
			mx = max(mx, solve(1, rare[i]));
		}
	}

	fin(mx);
}

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

int N,D;
LL res=-INF;
LL Day[300];
LL mem[300][100000];
clothes T;
int i;

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