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

using namespace std;

int main(){
	int i,j,k,most,d,n,x,m;
	int dp[201][201];
	int t[201],a[201],b[201],c[201];

	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",&a[i],&b[i],&c[i]);
	for(i=0;i<d;i++) for(j=0;j<n;j++) dp[i][j]=-1;
	j=0;
	for(i=0;i<n;i++){
		if(a[i]<=t[0] && t[0]<=b[i]){
			dp[0][j]=i;
			j++;
		}
	}
	x=j;
	for(i=0;i<x;i++){
		for(j=1;j<d;j++){
			most=-1;
			for(k=0;k<n;k++){
				if(a[k] <= t[j] && t[j] <= b[k]){
					if(most<abs(c[dp[j-1][i]]-c[k])){
						dp[j][i]=k;
						most=abs(c[dp[j-1][i]]-c[k]);
					}
				}
			}
		}
	}
	for(i=0;i<x;i++){
		for(j=0;j<d;j++) printf("%d ",dp[j][i]);
		printf("\n");
	}
	most=0;
	for(i=0;i<x;i++){
		m=0;
		for(j=1;j<d;j++){
			m+=abs(c[dp[j-1][i]]-c[dp[j][i]]);
		}
		most=max(most,m);
	}
	printf("%d\n",most);
	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;

struct clothes{
    LL A[100];
    LL B[100];
    LL C[100];
};
static const LL INF = 1<<25;
int N,D;
LL ans;
LL Day[100];
LL res;
clothes  T;

LL cal(LL day,LL p,LL pp){
    cout<<day<<" "<<p<<" "<<pp<<endl;
   if(day==N)return abs(pp-p);
   FOR(i,1,D){
       if(day==0){
            if(Day[1]>=T.A[i]&&Day[1]<=T.B[i])
            res=cal(day+1,T.C[i],p);
       }
       else if(Day[day+1]>=T.A[i]&&Day[day+1]<=T.B[i]){
            if(day>1)res=cal(day+1,T.C[i],p)+abs(pp-p);
            else res=cal(day+1,T.C[i],p);
       }
   }
   if(ans<res)ans=res;
   return ans;
}


int main(){
    cin>>N>>D;
    cout<<INF<<endl;
    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)<<endl;
}

C++: #include<iostream>
#include<cstdlib>
using namespace std;

int t[205];
int d;
int n;
int garment[205][3];
int dp[205][205];
int ans;

int dfs(int, int);

int main()
{
  for(int i = 0; i < 205; i++)
  {
    for(int j = 0; j < 65; j++)
      dp[i][j] = -1;
  }

  cin >> d >> n;
  for(int i = 0; i < d; i++)
    cin >> t[i];
  for(int i = 0; i < n; i++)
    cin >> garment[i][1] >> garment[i][2] >> garment[i][0];

  for(int i = 0; i < n; i++)
  {
    if(t[0] >= garment[i][1] && t[0] <= garment[i][2])
    {
      ans = max(dfs(i, 1), ans);
    }
  }
  cout << ans << endl;
}

int dfs(int last, int day)
{
  //cout << " -- day" << day + 1 << " t" << t[day] << endl; 
  if(dp[last][day] != -1)
  {
    //cout << "dp" << endl;
    return dp[last][day];
  }  
  if(day == d)
  {
    //cout << "return " << day + 1 << endl;
    return 0;
  }

  int r = 0;
  for(int i = 0; i < n; i++)
  {
    //cout << garment[i][1] << " - " << garment[i][2] << ": " << garment[i][0]; 
    if(t[day] >= garment[i][1] && t[day] <= garment[i][2])
    {  
      //cout << "OK\n";
      r = max(dfs(i, day + 1) + abs(garment[i][0] - garment[last][0]), r);
      //cout << "----" << endl;
    }
    //else
      //cout << "NG\n";
  }
  dp[last][day] = r;
  return r;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#define loop(i,b,n) for(int i = b; i<n; i++)
#define rep(i,n)  loop(i,0,n)
#define INF 10000
using namespace std;

int main (){
    
    int d,number;
    int temp[202] = {0};
    int dp[500][500];
    rep(i,500)
        rep(j,500)
    dp[i][j] = -INF;
     //(x,y) = (day,hade)
    int Min[210],Max[210],c[210];
   // bool check[500][500];
    /*rep(i,501)
       rep(j,501)
            check[i][j] = false;*/
    cin  >> d >> number;
    rep(i,d)
        cin >> temp[i+1];
    rep(i,number)
        cin >> Min[i+1] >> Max[i+1] >> c[i+1];
    loop(j,0,d+1)//day
    {
        
        loop(k,0,number+1)// k
        {
            if(Min[k] <= temp[j] && temp[j] <=Max[k])
            {
                if(j == 1)
                    dp[j][c[k]] = 0;
                else
                {
                    dp[j][c[k]] = 0;
                    loop(l,0,500)
                    {
                        if(dp[j-1][l] != -INF)
                        {
                            dp[j][c[k]] = max(abs(c[k]-l)+dp[j-1][l],dp[j][c[k]]);
                            //cout << abs(c[k]-l)<< " " ;
                        }
                        
                        
                    }
                    
                    
                }	
            }
            
        }
        
    }
    
    int answer = 2;
    rep(i,500)
        answer = max(answer,dp[d][i]);
    cout << answer << endl;
    
    return 0;
}

C++: #include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

template<class T> inline void chmax(T& a, const T& b) { if(b > a) a = b; }

int d, n;
vector<int> a, b, c, t;

int memo[200][101];
int dfs(int day, int prev) {
	if(day == d)
		return 0;

	if(memo[day][prev] != -1)
		return memo[day][prev];

	int res = 0;
	for(int i = 0; i < n; ++i)
		if(a[i] <= t[day] && t[day] <= b[i])
			chmax(res, abs(prev - c[i]) + dfs(day + 1, c[i]));

	return memo[day][prev] = res;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> d >> n;

	t.resize(d);
	for(int i = 0; i < d; ++i)
		cin >> t[i];

	a.resize(n);
	b.resize(n);
	c.resize(n);
	for(int i = 0; i < n; ++i)
		cin >> a[i] >> b[i] >> c[i];

	memset(memo, -1, sizeof(memo));
	int ans = 0;
	for(int i = 0; i < n; ++i)
		if(a[i] <= t[0] && t[0] <= b[i])
			chmax(ans, dfs(1, c[i]));

	cout << ans << endl;

	return EXIT_SUCCESS;
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

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,-1) );
  for(int i=0;i<n;i++){
    if(a[i] <= t[0] && t[0] <= b[i])dp[0][i] = 0;
  }

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

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