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 <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Cloth {
    int lb;
    int ub;
    int hade;
    Cloth(int ub, int lb, int hade) :
        ub(ub), lb(lb), hade(hade) {}
};

int main(){
    int d,n;
    cin >> d >> n;
    vector<int> temp(d);
    vector<Cloth> cloth(n, Cloth(0,0,0));
    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;
        cloth[i].ub = b;
        cloth[i].lb = a;
        cloth[i].hade = c;
    }

    int p1 = 0, p2 = 0;
    int b1 = 0, b2 = 10000000;
    for(int i=0;i<d;++i) {
        int c1 = 0, c2 = 0;
        int a1 = 0, a2 = 0;
        int t = temp[i];
        for(int j = 0; j<n; ++j) {
            if( cloth[j].lb <= t && t <= cloth[j].ub ) {
                int h = cloth[j].hade;
                if( i == 0) {
                    b1 = max(b1,h);
                    b2 = min(b2,h);
                } else {
                    if( c1 <= abs(b1-h) ) {
                        c1 = abs(b1-h);
                        a1 = h;
                    }
                    if( c2 <= abs(b2-h) ) {
                        c2 = abs(b2-h);
                        a2 = h;
                    }
                }
            }
        }
        if(i >= 1) {
            p1 += c1;
            p2 += c2;
            b1 = a1; b2 = a2;
        }
    }
    cout << max(p1,p2) << endl;

    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

int d, n;
int t[202];
int po[70][2];

int dfs(int i=0, int cost=0, int front=0)
{
  if (i == d) return cost;
  if (i == 0){
    return max(dfs(i + 1, 0, po[t[i]][0]), dfs(i + 1, 0, po[t[i]][1]));
  }

  return max(dfs(i + 1, cost + abs(front - po[t[i]][0]), po[t[i]][0]), dfs(i + 1, cost + abs(front - po[t[i]][1]), po[t[i]][1]));
}

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

  for (int i = 0; i < 70; i++){
    po[i][0] = 1e9;
    po[i][1] = -1;
  }

  for (int i = 0; i < n; i++){
    int a, b, c;
    cin >> a >> b >> c;
    for (int l = a; l <= b; l++){
      po[l][0] = min(po[l][0], c);
      po[l][1] = max(po[l][1], c);
    }
  }

  cout << dfs() << endl;
}

C++: #include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int D,N;
	int i,j,k;
	int dp[201][201];
	int T[201],A[201],B[201],C[201];
	
	cin>>D>>N;
	
	for(i=1;i<=D;i++){
		cin>>T[i];
	}
	
	for(i=1;i<=N;i++){
		cin>>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<=N;i++){
		if(A[i]<=T[1]&&T[1]<=B[i]){
			dp[1][i]=0;
		}
	}
	
	/*for(i=1;i<=D;i++){
		for(j=1;j<=N;j++){
			cout<<dp[i][j];
		}
		cout<<endl;
	}*/
	
	int sum=0;
	for(i=1;i<D;i++){
		for(j=1;j<=N;j++){
			if(dp[i][j]!=-1){
				for(k=1;k<=N;k++){
					if(A[k]<=T[i+1]&&T[i+1]<=B[k]){
						sum=abs(C[j]-C[k]);
						dp[i+1][k]=max(dp[i+1][k],dp[i][j]+sum);
					}					
				}
			}
		}
	}
	
/*	for(i=1;i<=D;i++){
		for(j=1;j<=N;j++){
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}*/
	int MAX=-1;
	for(i=1;i<=N;i++){
		MAX=max(MAX,dp[D][i]);
	}
	cout<<MAX<<endl;
	
	
	return 0;
}

C++: #include<stdio.h>
#include<stdlib.h>

struct str
{
	int a, b, c;
};
int t[200];
str b[200];
str dp[200];
int main(){
	int d, n;
	scanf("%d%d", &d, &n);
	for (int i = 0; i < d; i++)
		scanf("%d", &t[i]);
	for (int i = 0; i < n; i++){
		int a_, b_, c_;
		scanf("%d%d%d", &a_, &b_, &c_);
		b[i].a = a_;
		b[i].b = b_;
		b[i].c = c_;
	}
	int min = 101;
	for (int i = 0; i < n; i++)
		if (b[i].a <= t[0] && t[0] <= b[i].b&&min > b[i].c)
			min = b[i].c;
	dp[0].a = 0; dp[0].b = min;
	for (int i = 1; i < d; i++){
		int max = 0;
		for (int j = 0; j < n; j++){
			if (b[j].a <= t[i] && t[i] <= b[j].b&&abs(dp[i - 1].b - b[j].c) >= max){
				max = abs(dp[i - 1].b - b[j].c);
				dp[i].b = b[j].c;
			}
		}
		dp[i].a = dp[i - 1].a + max;
	}
	printf("%d\n", dp[d - 1]);
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int a[1999],b[1999],c[1999],D,N,t[1999],da[1999];
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 huku=0,ka=0;
    for(int i=0;i<D;i++){
         int kari=0,kari2=114514;

        for(int j=0;j<N;j++){
            if(a[j]<=t[i]&&t[i]<=b[j])kari=max(kari,c[j]);
            if(a[j]<=t[i]&&t[i]<=b[j])kari2=min(kari2,c[j]);
        }
        int kura1=0,kura2=0;
        if(i==0){kari=kari2;}
        if(i-1>=0){
            kura1=da[i-1]-kari;
            kura2=da[i-1]-kari2;
        }
        if(kura1<0)kura1=kura1*-1;
        if(kura1<0)kura2=kura2*-1;
        if(kura1<kura2){kari=kari2;}

        da[i]=kari;

    }
    
    for(int i=1;i<D;i++){
        int kaz=0;
        kaz=da[i-1]-da[i];
        if(kaz<0)kaz=kaz*-1;
        huku+=kaz;
    }
    cout<<huku<<endl;





}

C++: #include<iostream>
#include<algorithm>
using namespace std;
const int A=0;
const int B=1;
const int C=2;
const int INF=45451919;
int D,N;
int temp[201],huku[201][3];
int dp[201][201];


int main(){
	cin>>D>>N;
	for(int i=1;i<=D;i++)cin>>temp[i];
	for(int i=1;i<=N;i++)cin>>huku[i][A]>>huku[i][B]>>huku[i][C];
	//for(int i=1;i<=N;i++)cout<<huku[i][A]<<huku[i][B]<<huku[i][C]<<endl;
	for(int i=0;i<201;i++)for(int j=0;j<201;j++)dp[i][j]=-1;
	for(int i=1;i<=N;i++)if(huku[i][A]<=temp[1]&&huku[i][B]>=temp[1])dp[1][i]=0;
	
	
//		for(int j=0;j<10;j++)
//	cout<<huku[j][C]<<"  ";
//	cout<<endl;
	
for(int i=1;i<=D;i++){
	for(int j=1;j<=N;j++){
		if(huku[j][A]<=temp[i]&&huku[j][B]>=temp[i]){
			for(int k=1;k<=N;k++){
				if(huku[k][A]<=temp[i+1]&&huku[k][B]>=temp[i+1]){
					dp[i+1][k]=max(abs(huku[k][C]-huku[j][C])+dp[i][j],dp[i+1][j]);
					}
			}
		}
	}
}
	//デバッグ
		/*for(int i=1;i<=D;i++){
		for(int j=1;j<=N;j++){
			cout<<dp[i][j]<<" ";
		}*/
		int ans=0;
		for(int i=1;i<=N;i++)ans=max(ans,dp[D][i]);
			cout<<ans<<endl;
	
return 0;
}

C++: #include<algorithm>
#include<iostream>
#include<math.h>
#include<limits.h>

int D, N;
int T[200];
int A[200], B[200], C[200];
// suit[i][j]: i日目に服jが着れるか
bool suit[200][200];
// dp[i][j]: i日目までで当日に服jを選んだ場合の派手さの差の絶対値の合計
int dp[201][201];

int main()
{
	std::cin >> D >> N;
	for( int i = 0; i < D; i++ )
		std::cin >> T[i];

	for( int j = 0; j < N; j++ )
		std::cin >> A[j] >> B[j] >> C[j];

	for( int i = 0; i < D; i++ )
		for( int j = 0; j < N; j++ )
			suit[i][j] = ( A[j] <= T[i] && T[i] <= B[j] );

	for( int i = 0; i < D; i++ )
		for( int j = 0; j < N; j++ )
			dp[i][j] = INT_MIN;

	// 1日目で着れる服は0
	for( int j = 0; j < N; j++ )
		if( suit[0][j] )
			dp[0][j] = 0;

	// i日目
	for( int i = 0; i < D - 1; i++ )
		// 当日に選んだ服j
		for( int j = 0; j < N; j++ )
			// 前日に選んだ服k
			for( int k = 0; k < N; k++ )
				if( suit[i+1][j] )
					dp[i+1][j] = std::max( dp[i+1][j], dp[i][k] + abs( C[j] - C[k] ) );

	int ans = 0;
	for( int j = 0; j < N; j++ )
		ans = std::max( ans, dp[D-1][j] );

	std::cout << ans << std::endl;

	return 0;
}