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++)
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 mem[day][pp];
   }
    if(day<=1){
       FOR(i,1,D){
            if(Day[day]>=A[i]&&Day[day]<=B[i]){
            res=cal(day+1,i);
         }
      }
   }
   else{
        FOR(i,1,D){
            if(Day[day]>=A[i]&&Day[day]<=B[i]){
                int temp=abs(C[pp]-C[i]);
                res=max(cal(day+1,i)+temp,res);
                mem[day][pp]=res;
            }
        }
   }
   return mem[day][pp]=res;
}

int main(){
    cin>>N>>D;
    memset(mem,-1,sizeof(mem));
    FOR(i,1,N){
        cin>>Day[i];
    }
    FOR(i,1,D){
        cin>>A[i]>>B[i]>>C[i];
    }
    int ans=0
    FOR(i,1,D){
        if(Day[1]>=A[i]&&Day[1]<=B[i]){
            ans=max(cal(1,i),ans)<<endl;
        }
    }
    return 0;
}

C++: #include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

#define MAX 200
#define MAX_T 60
typedef pair<int,int> P;

int T[MAX],D,dp[MAX][MAX];
vector<P> vec[MAX_T+1];

int solve(int d,P prev){
  if(d == D) return 0;
  if(dp[d][prev.second] >= 0) return dp[d][prev.second];
  int res = 0;
  for(int i = 0 ; i < (int)vec[T[d]].size() ; i++){
    int diff = abs(vec[T[d]][i].first-prev.first);
    res = max(res,solve(d+1,vec[T[d]][i])+diff);
  }
  return dp[d][prev.second] = res; 
}

int main(){
  int N,A,B,C;
  memset(dp,-1,sizeof(dp));

  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",&A,&B,&C);
    for(int j = A ; j <= B ; j++){
      vec[j].push_back(P(C,i));
    }
  }
  int ans = 0;
  for(int i = 0 ; i < (int)vec[T[0]].size() ; i++){
    ans = max(ans,solve(1,vec[T[0]][i]));
  }
  printf("%d\n",ans);

  return 0;
}

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

using namespace std;

#define rep(i, n) for (int i=0; i<int(n); i++)
#define all(c) (c).begin(), (c).end()

#define MAX_D 210
#define MAX_N 210

int D, N;
int T[MAX_D];
int A[MAX_N];
int B[MAX_N];
int C[MAX_N];

int dp[MAX_D][101]; // last_score

int main() {
  cin >> D >> N;
  rep(i, D) cin >> T[i];
  rep(i, N) cin >> A[i] >> B[i] >> C[i];

  rep(i, D) rep(j, 101) dp[i][j] = -1;
  dp[0][0] = 0;
  rep(day, D) {
    rep(k, 101) {
      rep(i, N) {
        if (dp[day][k] != -1) {
          int temp = T[day];
          if (A[i] <= temp && temp <= B[i]) {
            int x = C[i];
            if (day == 0) dp[day+1][x] = dp[day][k];
            else          dp[day+1][x] = max(dp[day+1][x], dp[day][k] + abs(x-k));
          }
        }
      }
    }
  }

  int ans = 0;
  rep(k, 101) ans = max(ans, dp[D-1+1][k]);
  cout << ans << "\n";
  return 0;
}

C++: #include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
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=mem[day][pp];
   if(day==N+1){
        return res=0;
   }
   if(mem[day][pp]!=-1){
        return mem[day][pp];
   }
   if(day<=1){
       FOR(i,1,D){
            if(Day[day]>=A[i]&&Day[day]<=B[i]){
            res=cal(day+1,C[i]);
         }
      }
   }
   else{
        FOR(i,1,D){
            if(Day[day]>=A[i]&&Day[day]<=B[i]){
                int temp=abs(pp-C[i]);
                res=max(cal(day+1,C[i])+temp,res);
                mem[day][pp]=res;
            }
        }
   }
   return mem[day][pp]=res;
}

int main(){
    cin>>N>>D;
    memset(mem,-1,sizeof(mem));
    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<stdio.h>
#include<stdlib.h>
int h[201][201];
int main(void)
{
    int n,m,i,j,x[200],a[200],b[200],c[200],l,s,w,f;
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++){
	    scanf("%d",&x[i]);
	}
	for(i=0;i<m;i++){
	    scanf("%d %d %d",&a[i],&b[i],&c[i]);
	}
	for(i=0;i<n;i++){
	    for(j=0;j<m;j++){
		    h[i][j]=-1;
		}
	}
	for(i=0;i<n;i++){
	    for(j=0;j<m;j++){
		    if(x[i]>=a[j]&&x[i]<=b[j]){
			    h[i][j]=c[j];
			}
		}
	}
	w=0;
	for(i=0;i<n-1;i++){
	    s=0;
		for(j=0;j<m;j++){
		    for(l=0;l<m;l++){
			    f=abs(h[i][j]-h[i+1][l]);
				if(h[i][j]>-1&&h[i+1][l]>-1&&s<f){
				    s=f;
					printf("%d %d %d %d\n",i,j,l,s);
				}
			}
		}
		w+=s;
	}
	printf("%d\n",w);
	return 0;
}

C++: #include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
double EPS=1e-8;
int INF = 1e9;
int dp[200][200];
int main(){
	int n,t[200],a[200],b[200],c[200],d;
	cin>>d>>n;
	REP(i,d)cin>>t[i];
	REP(i,n)cin>>a[i]>>b[i]>>c[i];
	REP(i,n)REP(j,n){
		if(a[i]<=t[0]&&t[0]<=b[i]&&a[j]<=t[1]&&t[1]<=b[j]){
			dp[1][j]=max(dp[1][j],abs(c[i]-c[j]));
		}
	}
	for(int i=2;i<d;i++)
		REP(j,n)
			if(a[j]<=t[i]&&t[i]<=b[j])
				REP(k,n)dp[i][j]=max(dp[i][j],dp[i-1][k]+abs(c[j]-c[k]));
	int ans=0;
	REP(i,n)ans=max(ans,dp[d-1][i]);
	cout<<ans<<endl;
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < int(n); ++i)

int dp[201][200];

int main() {
  int d, n;
  cin >> d >> n;
  int t[d], a[n], b[n], c[n];
  rep (i, d) cin >> t[i];
  rep (i, n) cin >> a[i] >> b[i] >> c[i];
  rep (i, d - 1) rep (j, n) if (a[j] <= t[i + 1] && t[i + 1] <= b[j]) rep (k, n) if (a[k] <= t[i] && t[i] <= b[k]) {
	dp[i + 1][j] = max(dp[i + 1][j], dp[i][k] + (int)abs(c[j] - c[k]));
      }
  int res = 0;
  rep (i, n) res = max(res, dp[d - 1][i]);
  cout << res << endl;
}