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 <bits/stdc++.h>

using namespace std;

typedef struct {
	int a;
	int b;
	int c;
} fuku_t;

int d, n;

int t[200];
fuku_t fuku[200];

int dp[200][200];

int main()
{
	cin >> d >> n;

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

	for (int i = 0; i < n; ++i) scanf("%d %d %d", &fuku[i].a, &fuku[i].b, &fuku[i].c);

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

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

	int ans = 0;

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

	printf("%d\n", ans);
}

C++: #include <bits/stdc++.h>

using namespace std;

int n, d;
int t[200];
int a[200], b[200], c[200];
int dp[201][200];


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

	int ma = 0;

	for (int i = 0; i < n; ++i) ma = max(ma, dp[d - 1][i]);

	cout << ma << endl;
}

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 temp;
int cal(int day,int pp){
   int res=mem[day][pp];
   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]){
            temp=abs(pp-C[i]);
            if(day==1){
                res=cal(day+1,C[i]);
            }
            else {
                res=max(cal(day+1,C[i])+abs(pp-C[i]),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>
using namespace std;int P[250][150],T[250],x[250][3],D,N,M,i,j,k;
main(){memset(P,-999999,sizeof(P));cin>>D>>N;
for(i=1;i<=D;i++){cin>>T[i];}
for(i=1;i<=N;i++){cin>>x[i][0]>>x[i][1]>>x[i][2];if(T[1]>=x[i][0] && T[1]<=x[i][1]){P[1][x[i][2]]=0;}}
for(i=2;i<=D;i++){for(j=1;j<=N;j++){if(T[i]>=x[j][0] && T[i]<=x[j][1]){
for(k=0;k<=100;k++){P[i][x[j][2]]=max(P[i][x[j][2]],P[i-1][k]+abs(x[j][2]-k));}}}}
for(i=0;i<=100;i++){M=max(M,P[D][i]);}cout<<M<<"\n";}

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=-INF;
LL Day[100];
LL res;
clothes  T;

LL cal(LL day,LL p,LL pp){
   if(day==0)return abs(pp-p);
   FOR(i,1,D){
       if(Day[day]>=T.A[i]&&Day[day]<=T.B[i]){
            if(day<N-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;
    FOR(i,1,N){
        cin>>Day[i];
    }
    FOR(i,1,D){
        cin>>T.A[i]>>T.B[i]>>T.C[i];
    }
    cout<<cal(N,0,0)<<endl;
}

C++: #include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>P;
typedef pair<P,int> PP;

int dp[333][333];

int main(){
	int d,n;
	cin>>d>>n;
	int temp[333];
	PP wear[333];
	
	for(int i=0;i<300;i++)
	for(int j=0;j<300;j++)dp[i][j]=-1;
	
	for(int i=0;i<d;i++)cin>>temp[i];
	
	for(int i=0;i<n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		wear[i]=make_pair(make_pair(a,b),c);
		}
		
		for(int i=0;i<n;i++){
			if(wear[i].first.first<=temp[0]&&temp[0]<=wear[i].first.second){
				dp[1][i]=0;
				}
			}
			
			for(int td=2;td<=d;td++){//today
				for(int i=0;i<n;i++){
					if(wear[i].first.first<=temp[td-1]&&temp[td-1]<=wear[i].first.second){
						dp[td][i]=0;
						}
					}
					
					for(int i=0;i<n;i++){
						for(int j=0;j<n;j++){
							if(dp[td-1][i]!=-1&&dp[td][j]!=-1){
								dp[td][j]=max(dp[td][j],dp[td-1][i]+abs(wear[i].second-wear[j].second));
								}
							}
						}
				}
				
		int ans=0;
		for(int i=0;i<300;i++){
			ans=max(ans,dp[d][i]);
			}	
		cout<<ans<<endl;
		return 0;		
	}

C++: #include<iostream>
#include<algorithm>
#include<cmath>
#define INF 1<<28
using namespace std;

int a[222], b[222], c[222];
int d, n;
int t[222];
int memo[222][222];

int solve(int p, int q){
  if(p == d-1) return 0;
  if(memo[p][q]) return memo[p][q];
  
  int ret = -INF;
  for(int i=0;i<n;i++) 
    if(a[i] <= t[p+1] && t[p+1] <= b[i])
      ret = max(solve(p+1, i)+abs(c[q]-c[i]), ret);
  
  return memo[p][q] = ret;
}

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];
  
  int ans = -INF;
  for(int i=0;i<n;i++)
    if(a[i] <= t[0] && t[0] <= b[i])
      ans = max(solve(0, i), ans);
  
  cout << ans << endl;
}

C++: #include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
#define P pair<int, int>
#define F first
#define S second
#define mod 1000000007
#define INF 9000000000000000000
signed main(void) {
    int d,n;cin>>d>>n;
    int D[d];rep(i,d)cin>>D[i];
    tuple<int,int,int>V[n];
    rep(i,n){
        int a,b,c;
        cin>>a>>b>>c;
        V[i]=make_tuple(a,b,c);
    }
    vector<vector<int>>dp(d,vector<int>(n,-INF));
    vector<int>Day[d];
    rep(i,d){
        rep(j,n){
            int a,b,c;
            tie(a,b,c)=V[j];
            if(a<=D[i]&&D[i]<=b)Day[i].push_back(c);
        }
    }
    rep(i,n)dp[0][i]=0;
    rep(i,d-1){
        rep(j,Day[i].size()){
            rep(k,Day[i+1].size()){
                dp[i+1][k]=max(dp[i+1][k],dp[i][j]+abs(Day[i+1][k]-Day[i][j]));
            }
        }
    }
    int ans=-INF;
    rep(i,n)ans=max(ans,dp[d-1][i]);
    cout<<ans<<endl;
    
    
    
}